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,u∈V , 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,u∈V 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 ∗ ∈ X
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?
Respuestas:
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,⊙)
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 ( xx∈X PO ) 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 )y∈F(x) Z(x,y)=⊙{Z(x,y′)∣y′∈F(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".PE PO x∈X Opt(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 ∈ XPD PO (x,k) x∈X 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 )k∈Q x y Z(x,y)≤k ⊙=min ≥ k si ⊙ = máx .Z(x,y)≥k ⊙=max
Una primera observación es ahora que P O ∈ N P O ⇒ P D ∈ N P . La prueba no es difícil y se omite aquí.PO∈NPO⇒PD∈NP
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.PE PD PO PO
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 1 ⇔ f ( 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 2L1 L2 f x x∈L1⇔f(x)∈L2 L1 L2 L1≤mL2 . 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.P P
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 .P1 P2 P1≤TP2 P1 P2
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:≤m P1≤TP2 P1 P2 P2 P1 ≤T
Deje P O ∈ N P O , entonces P D ≤ T P E ≤ T P O .PO∈NPO PD≤TPE≤TPO
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 2 ≤ P 1 se mantienen, escribimos P 1 ≡ T P 2 ; Nuestra noción de equivalencia .P1 P2 P1≤TP2 P2≤P1 P1≡TP2
Ahora estamos listos para probar que P D ≡ T P E dado el problema de optimización correspondiente es P O ∈ N 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 NPD≡TPE PO∈NPO Z PE≤TPD ⊙{Z(x,y)∣y∈F(x)} PD P 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.PO PE PD≡TPE≡TPO
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 .≤m ≤T ≤m
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. ◻P P′ P≤mP′⇒P≤TP′ □
Ahora estamos listos para el final:
Deje P O ∈ N 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 ' O ∈ N P O tal que P O ≤ T P ' E . Entonces tenemosPO∈NPO Z PD
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,… Σ∗ w0 y∈Σ∗ σ(y) i y=wi σ and σ−1σ−1 can be computed in polynomial time. Let qq be a polynomial such that for all x∈Xx∈X and all y∈F(x)y∈F(x) we have σ(y)<2q(|x|)σ(y)<2q(|x|) .
Now the problem P′OP′O is identical to POPO except for a modified objective function Z′Z′ . For x∈Xx∈X and y∈F(x)y∈F(x) we take Z′(x,y)=2q(|x|)⋅Z(x,y)+σ(y)Z′(x,y)=2q(|x|)⋅Z(x,y)+σ(y) . Z′Z′ is computable in polynomial time thus P′O∈NPOP′O∈NPO .
To show that PO≤TP′EPO≤TP′E we observe that xx is feasible for POPO if and only if it is feasible for P′EP′E . We can assume that this is the case, since the opposite case is trivial to handle.
The substituion of Z′Z′ for ZZ is monotonic in the sense that for all y1,y2∈F(x)y1,y2∈F(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 P′OP′O is an optimal solution of xx in POPO . Thus our task reduces to the computation of an optimal solution yy of xx in P′OP′O .
Querying the oracle for P′EP′E 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.
fuente
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:
and a decision problem for 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)∣x∈L}.
† This depends on S. If, for instance, S is bounded, there might exists an algorithm that does stop.
fuente