Versión de optimización de problemas de decisión

26

Se sabe que cada problema de optimización / búsqueda tiene un problema de decisión equivalente. Por ejemplo, el problema del camino más corto

  • Versión de optimización / búsqueda: Dado un gráfico no ponderado no dirigido G = ( V , E )G=(V,E) y dos vértices v , u Vv,uV , encuentre la ruta más corta entre vv y uu .
  • versión de decisión: Dado un gráfico no ponderado no dirigido G = ( V , E )G=(V,E) , dos vértices v , u Vv,uV y un número entero no negativo kk , ¿hay una ruta en GG entre uu y vv cuya longitud sea como máximo kk ?

En general, "¡Encuentra x XxX st f ( x ) = min { f ( x ) x X }f(x)=min{f(x)xX} !" se convierte en "¿Hay st ?".x X f ( x ) kxXf(x)k

Pero, ¿también es cierto lo contrario, es decir, hay un problema de optimización equivalente para cada problema de decisión? Si no, ¿cuál es un ejemplo de un problema de decisión que no tiene un problema de optimización equivalente?

Luke Miles
fuente
66
¿Es este bit igual a cero?
JeffE
55
Debe explicar "equivalente" con más detalle, por ejemplo, ¿quiere decir que uno puede resolverse usando el otro como oráculo / caja negra en tiempo polinómico (o en espacio logarítmico)? ¿Te preocupan todos los problemas o solo los problemas dentro de N PNP ?
Kaveh
1
Dependiendo de su punto de vista, la pregunta es trivial (tome cualquier problema de decisión que no tenga una " k ") o no responda (¿cómo demostrar que no existe un "problema optativo equivalente"?). k
Raphael

Respuestas:

28

Como ya se dijo en los comentarios, depende de las definiciones, como de costumbre. Mi intento de responder esto necesita bastantes definiciones, por lo que este será otro ejemplo de mi incapacidad para dar respuestas concisas.


Definición: Un problema de optimización es una tupla ( X , F , Z , ) con(X,F,Z,)

  • X el conjunto deinstanciasoentradasadecuadamente codificadas (cadenas).X
  • F es una función que asigna cada instancia x X a un conjunto F ( x ) desoluciones factiblesde x .FxXF(x)x
  • Z es la función objetivo que asigna cada par ( x , y ) , donde x X e y F ( x ) , a un número real Z ( x , y ) llamadovalorde y .Z(x,y)xXyF(x)Z(x,y)y
  • es ladirección de optimización, min o max .minmax

Definición: Una solución óptima de una instancia x X de un problema de optimización P O es una solución factible y F ( xxXPO ) para la cual Z ( x , y ) = { Z ( x , y ) y F ( x ) } . El valor de una solución óptima se denota con O p t ( x )yF(x)Z(x,y)={Z(x,y)yF(x)}Opt(x)y llamó al óptimo .

Definición: El problema de evaluación , denotado P E , que corresponde al problema de optimización P O es el siguiente: Dada una instancia x X , calcule O p t ( x ) si x tiene una solución óptima y, de lo contrario, genera "no solución óptima".PEPOxXOpt(x)x

Tenga en cuenta que esto solo pide el valor de la solución óptima, no toda la solución en sí con todos sus detalles.

Definición: El problema de decisión , denotado P D correspondiente al problema de optimización P O es el siguiente: Dado un par ( x , k ) , donde x XPDPO(x,k)xX y k Q , decida si x tiene una solución factible y tal que Z ( x , y ) k si = min y tal que Z ( x , y )kQxyZ(x,y)k=mink si= máx .Z(x,y)k=max

Una primera observación es ahora que P ON P OP DN P . La prueba no es difícil y se omite aquí.PONPOPDNP

Ahora intuitivamente P E y P D correspondiente a P O no son más difíciles que P O sí mismo. Para expresar este sentimiento formalmente (definiendo así qué equivalente se supone que significa) usaremos reducciones.PEPDPOPO

Recuerde que un lenguaje L 1 es reducible en tiempo polinómico a otro lenguaje L 2 si hay una función f , computable en tiempo polinomial, tal que para todas las palabras x , x L 1f ( x ) L 2 . Este tipo de reducibilidad se conoce como Karp o reducibilidad de muchos a uno , y si L 1 es reducible a L 2 de esta manera, lo expresamos escribiendo L 1 m L 2L1L2fxxL1f(x)L2L1L2L1mL2. Este es un concepto central en la definición de completitud NP.

Desafortunadamente, las reducciones de muchos a uno van entre idiomas y no está claro cómo emplearlos en el contexto de los problemas de optimización. Por lo tanto, debemos considerar un tipo diferente de reducibilidad, la reducibilidad de Turing . Primero necesitamos esto:

Definición: Un oráculo para un problema P es una subrutina (hipotética) que puede resolver instancias de P en tiempo constante.PP

Definición: Un problema P 1 es Turing -tiempo polinómico reducible a un problema P 2 , escrito P 1 T P 2 , si las instancias de P 1 pueden resolverse en tiempo polinomial mediante un algoritmo con acceso a un oráculo para P 2 .P1P2P1TP2P1P2

Informalmente, al igual que con m , la relación P 1 T P 2 expresa que P 1 no es más difícil que P 2 . También es fácil ver que si P 2 puede resolverse en tiempo polinómico, también puede P 1 . De nuevo T es una relación transitiva. El siguiente hecho es obvio:mP1TP2P1P2P2P1T

Deje P ON P O , entonces P D T P E T P O .PONPOPDTPETPO

Porque dada la solución completa, calcular su valor y decidir si cumple con el límite k es simple.k

Definición: Si para dos problemas P 1 y P 2 ambas relaciones P 1 T P 2 , P 2P 1 se mantienen, escribimos P 1 T P 2 ; Nuestra noción de equivalencia .P1P2P1TP2P2P1P1TP2

Ahora estamos listos para probar que P D T P E dado el problema de optimización correspondiente es P ON P O y Z tiene un valor entero. Tenemos que demostrar que P E T P D se cumple. Podemos determinar { Z ( x , Y ) | Y F ( x ) } con una búsqueda binaria usign la Orcale de P D . La definición de NPDTPEPONPOZPETPD{Z(x,y)yF(x)}PDP ONPO asegura que | Z(x,y) | 2 q ( | x | ) para algún polinomioq, por lo que el número de pasos en la búsqueda binaria es polinomial en | x | . |Z(x,y)|2q(|x|)q|x|

Para un problema de optimización P O, la relación con P E es menos clara. En muchos casos concretos, se puede demostrar directamente que P D T P E T P O . Para demostrar que esto se cumple generalmente dentro del marco dado aquí, necesitamos una suposición adicional.POPEPDTPETPO

Primero necesitamos extender m de pares de idiomas a pares de los problemas de decisión correspondientes. Entonces es fácil ver que T es más general que m .mTm

Sean P y P ' problemas de decisión; entonces P m P P T P . Esto se cumple porque una reducción de muchos a uno puede interpretarse como el uso de un oráculo de una manera muy restringida: el oráculo se llama una vez, al final, y su resultado también se devuelve como el resultado general. PPPmPPTP

Ahora estamos listos para el final:

Deje P ON P O y supongamos Z es un número entero de valor y que P D es NP-completo, entonces P D T P E T P O . Con las observaciones anteriores se mantiene para mostrar P O T P E . Para ello vamos a exhibir un problema P ' ON P O tal que P O T P ' E . Entonces tenemosPONPOZPD

PDTPETPO.
POTPEPONPOPOTPEP O T P ' ET P ' DT P D T P E . El segundo y el tercerT se mantienen debido a la equivalencia de la versión de decisión y evaluación comprobada anteriormente. La terceraT se deduce de la completitud NP de P D y los dos hechos mencionados anteriormente, a saber, P ON P OP DN P y P m
POTPETPDTPDTPE.
TTPDPONPOPDNPP ' OP T P ' O .PmPOPTPO

Ahora los detalles: suponga que las soluciones factibles de P O están codificadas usando un alfabeto Σ equipado con un orden total. Sean w 0 , w 1 , ... las palabras de Σ enumeradas en orden de longitud no decreciente y orden lexicográfico dentro de los bloques de palabras con longitud común. (Por lo tanto, w 0 es la palabra vacía.) Para todos y Σ dejemos que σ ( y ) denote el entero único i tal que y = w i . Ambos σPOΣw0,w1,Σw0yΣσ(y)iy=wiσ and σ1σ1 can be computed in polynomial time. Let qq be a polynomial such that for all xXxX and all yF(x)yF(x) we have σ(y)<2q(|x|)σ(y)<2q(|x|).

Now the problem POPO is identical to POPO except for a modified objective function ZZ. For xXxX and yF(x)yF(x) we take Z(x,y)=2q(|x|)Z(x,y)+σ(y)Z(x,y)=2q(|x|)Z(x,y)+σ(y). ZZ is computable in polynomial time thus PONPOPONPO.

To show that POTPEPOTPE we observe that xx is feasible for POPO if and only if it is feasible for PEPE. We can assume that this is the case, since the opposite case is trivial to handle.

The substituion of ZZ for ZZ is monotonic in the sense that for all y1,y2F(x)y1,y2F(x), if Z(x,y1)<Z(x,y2)Z(x,y1)<Z(x,y2) then Z(x,y1)<Z(x,y2)Z(x,y1)<Z(x,y2). This implies that every optimal solution for xx in POPO is an optimal solution of xx in POPO. Thus our task reduces to the computation of an optimal solution yy of xx in POPO.

Querying the oracle for PEPE we can get the value of Z(x,y)=2q(|x|)Z(x,y)+σ(y)Z(x,y)=2q(|x|)Z(x,y)+σ(y). Forming the remainder of this number modulo 2q(|x|)2q(|x|) yields σ(y)σ(y) from which yy can be computed in polynomial time.

uli
fuente
"An oracle for a problem P is a (hypothetical) subroutine that can solve instances of P in constant time." Must an oracle take only constant time?
Tim
@Tim Of course there are books, I listed a few in the comments of another answer
uli
@Tim Regarding the oracle: If you have found/conceived a reduction ATBATB between two problems AA and BB you have reduced the problem of finding an efficient algorithm for AA to finding an efficient algorithm for BB. Or in other words the reduction tells you that in order to solve AA you can use BB. It is like using a subroutine for BB in an algorithm for AA. However the problems AA and BB are often problems where we don’t know efficient solutions. And in case of Turing-reducibility we even use it in cases where the problems involved aren’t decidable at all.
uli
@Tim Thus BB is an unknown subroutine. It has become a custom in complexity theory to call the hypothetical algorithm for AA derived from the reduction as an algorithm with oracle BB. Calling the unknown subroutine for BB an oracle just expresses that we can’t hope to find an efficient algorithm for BB just as we can’t hope to obtain an oracle for BB. This choice is somewhat unfortunate, as it connotes a magical ability. The cost for the oracle should be |x||x| as a subroutine has at least to read the input xx.
uli
3
An excellent answer all around; the only thing I would add (coming at it now via another question) is that the 'optimization direction' is a needless bit of complexity and for concreteness we can always presume that the objective function Z is to be maximized; if the intention is to minimize, then we can just define a new objective function Z=Z and rewrite all the minimization of Z as maximization of Z.
Steven Stadnicki
5

As the comments say, the answer depends on the exact definitions. Let me interpret the question in a very basic (even naïve) way.

Let S be some relation, that is S{(a,b)a,bΣ}.

Now we define a search problem for S:

Given a, find a b such that (a,b)S.

and a decision problem for S:

Given (a,b) answer whether or not (a,b)S.

(for instance, in the example given in the question, S will hold all the pairs (u,v,k) such that there exists a path between u and v which is shorter than k.)

Note that these two problems are well defined. For this definition, we can ask whether the two problems are "equivalent" for any S. In "equivalent" I mean that if one of them is computable (i.e., there exists an algorithm that solves it) than the other one is computable as well. In general, they are not.

Claim 1: Decision implies Search.

Proof: Let DS be the algorithm that solves the decision problem of S. Given an input a, We can run DS(a,x) for any xΣ, one after the other, or in parallel. If there exists b such that (a,b)S, we will eventually find it. If not, the algorithm might not stop.

Claim 2: Search does not imply Decision.

The reason is that the search algorithm might return a different b than the one we need. That is, for every a there is some b that is very easy to find, but other b that is not. For instance, let L be some undecidable language, then define S={(x,0)xΣ}{(x,1)xL}.

For every x the search algorithm can return 0. But no decision algorithm can answer correctly whether (x,1)S, for all the pairs (x,1). If it could, it would have decided an undecidable problem, which is impossible.


This depends on S. If, for instance, S is bounded, there might exists an algorithm that does stop.

Ran G.
fuente
2
The right decision problem is existence of b s.t. a,bS.
Kaveh
If decision is defined as the existence of b, then search implies decision.
Ran G.
1
In a weak sense, i.e. w.r.t. computability but not complexity is a more delicate issue.
Kaveh