Los problemas de decisión frente a los problemas “reales” que no son de sí o no

Question

He leído en muchos lugares que algunos problemas son difíciles de aproximar (es NP-duro para aproximar ellos). Pero aproximación no es un problema de decisión: la respuesta es un número real y no Sí o No. También para cada factor de aproximación deseada, hay muchas respuestas que son correctas y muchos que están equivocados, y esto cambia con el factor de aproximación deseada

Entonces, ¿cómo se puede decir que este problema es NP-duro?

(inspirado en el segundo bala en Cómo es difícil contar el número de caminos simples entre dos nodos en una dirigida gráfica? )

Answer 1

Como usted ha dicho, no hay ninguna decisión que tomar, así que se necesitan nuevas clases de complejidad y nuevos tipos de reducciones para llegar a una definición adecuada de NP-dureza Optimización en problemas .

Una forma de hacer esto es tener dos nuevas clases NPO y PO que contiene problemas optimizaciones y mímica, por supuesto, las clases < problemas strong> NP y P para su decisión. Nuevas reducciones son necesarias también. Entonces podemos recrear una versión de NP-hard para problemas de optimización a lo largo de las líneas que fue un éxito para los problemas de decisión. Pero primero tenemos que poner de acuerdo en un optimización de problemas es.

Definición: Sea $ O = (X, L, M, opt) $ sea un optimización de problemas . $ X $ es el conjunto de entradas o casos codificada adecuada como cadenas. $ L $ es una función que mapea cada caso $ x \ in X $ en un conjunto de cadenas, los soluciones factibles de la instancia $ x $. Es un conjunto, porque hay muchas soluciones a una optimización de problemas. Por lo tanto no hemos un función objetivo $ f $ que nos dice que por cada par $ (x, y) $ $ y \ en L (x) $ de instancia y solución de su coste o valor . $ $ Opt nos dice si estamos maximizar o minimizar.

Esto nos permite definir lo que es un solución óptima es: Let $ y_ {opt} \ en L (x) $ será la solución óptima de una instancia $ x \ X $ en una optimización de problemas $ O = (X, L, M, opt) $ $$ con f (x, y_ {opt}) = \ {opt f (x, y) \ mediados y '\ en L (x) \} $$. La solución óptima es a menudo denotado por $ y ^ * $.

Ahora podemos definir la clase NPO : Let $ $ NPO el conjunto de todos los problemas de optimización-$ O = (X, L, M, opt) $ con:

1. $ X \ in P $
2. No es un polinomio p $ $ $ con | y | \ le p (| x |) $ para todas las instancias $ x \ in X $ y todas las soluciones factibles $ y \ en L (x) $. Además hay un algoritmo determinista que decide en tiempo polinómico si $ y \ en L (x) $.
3. $ f $ se puede evaluar en tiempo polinómico.

La intuición detrás de esto es:

1. Se puede verificar de manera eficiente si $ x $ es en realidad una instancia válida de nuestro problema de optimización.
2. El tamaño de las soluciones factibles está delimitada polinómicamente en el tamaño de las entradas, y podemos verificar de manera eficiente si $ y \ en L (x) es una solución de $ fesible de la instancia $ x $.
3. El valor de una solución de $ y \ in L (x) $ se puede determinar de manera eficiente.

Esto refleja cómo se define $ NP $, ahora para PO . Let $ PO $ el conjunto de todos los problemas de $ NPO $ que pueden ser resueltos por un algoritmo determinista en tiempo polinómico

Ahora estamos en condiciones de definir lo que se quiere llamar a un aproximación del algoritmo : Un aproximación del algoritmo de una optimización de problemas $ O = (X, L, f, opt) $ es un algoritmo que calcula una solución factible $ y \ in L (x) $ para una instancia $ x \ in X $.

Nota:. Que no nos preguntamos para un óptima solución que sólo lo que tenemos un factible un

Ahora tenemos dos tipos de errores: El error absoluto de una solución factible $ y \ in L (x) $ de una instancia $ x \ in X $ de la optimización de problemas $ O = (X, L, M, opt) es $ $ | f (x, y) f (x, y ^ *) |. $

llamar el error absoluto de una aproximación del algoritmo de $ A $ para la optimización de problemas $ O $ delimitada por $ k $ si el algoritmo $ A $ computa para cada instancia $ x \ in X $ una solución factible con una error absoluto limitada por $ k $.

Ejemplo: De acuerdo con el teorema de Vizing la índice cromático de un gráfico (el número de colores en el borde de colorante con el menor número de colores utilizados) es o bien $ \ Delta $ o $ \ delta + 1 $, donde $ \ Delta $ es el nodo de grado máximo. A partir de la demostración del teorema de una aproximación algoritmo se puede diseñar que calcula una ventaja colorear con $ \ Delta + 1 dólares colores. En consecuencia tenemos una aproximación del algoritmo para el $ \ {mathsf mínimo-EdgeColoring} $ - Problema en el que i error absolutos delimitada por $ 1 $.

Este ejemplo es una excepción, los pequeños errores absolutos son raros, así definimos el error relativo $ \ epsilon_A (x) $ de la aproximación del algoritmo $ A $ en la instancia $ x $ de la optimización de problemas $ O = (X, L, M, opt) $ con $ f (x, y)> 0 $ para todos $ x \ in X $ y $ y \ in L (x) $ a ser

$$ \ epsilon_A (x): = \ begin {casos} 0 y f (x, A (x)) = f (x, y ^ *) \\\ frac {| f (x, A (x)) -f (x, y ^ *) |} {\ max \ {f (x, A (x)), f (x, y ^ *) \}} y f (x, A (x)) \ ne f ( X, Y ^ *) \ end {casos} $$

donde $ A (x) = y \ in L (x) $ es la solución factible calculada por la aproximación del algoritmo $ A $.

Ahora podemos definir aproximación del algoritmo de $ A $ para la optimización de problemas $ O = (X, L, M, opt) $ para ser un $ \ delta $: Aproximación algoritmo para $ O $ si el error relativo $ \ epsilon_A (x) $ está delimitada por $ \ delta \ ge 0 $ para cada instancia $ x \ in X $, por lo tanto $$ \ epsilon_A (x) \ le \ delta \ qquad \ forall x \ in X. $$

La elección de $ \ max \ {f (x, A (x)), f (x, y ^ *) \} se selecciona $ en el denominador de la definición del error relativo para hacer la simétrica definición para maximizar y minimizar. El valor del error relativo $ \ epsilon_A (x) \ in [0,1] $. En caso de un problema de maximizar el valor de la solución nunca es menor que $ (1- \ epsilon_A (x)) \ cdot f (x, y ^ *) $ y nunca mayor que $ 1 / (1- \ epsilon_A (x) ) \ cdot f (x, y ^ *) $ para un problema de minimización.

Ahora podemos llamar a una optimización de problemas $ \ delta $ -approximable si hay un $ \ delta: Aproximación $-algoritmo de $ A $ por $ O $ que se ejecuta en tiempo polinómico.

No queremos mirar el error para cada caso $ x $, sólo nos fijamos en el peor de los casos. Así definimos $ \ epsilon_A (n) $, el relativ máxima de error de la aproximación del algoritmo de $ A $ para la optimización de problemas $ O $ para ser $$ \ epsilon_A (n) = \ sup \ {\ epsilon_A (x) \ mediados | x | \ le n \}. $$

Donde $ | x |. $ Debería ser el tamaño de la instancia

Ejemplo: Un acoplamiento máximo en un gráfico puede ser transformado en a un nodo mínimo de la cubierta $ C $ mediante la adición de todos los nodos de incidentes de la casación a la cubierta de vértice. Así $ de 1/2 \ cdot | C | $ bordes están cubiertos. Como cada cubierta vértice incluyendo la óptima debe tener uno de los nodos de cada borde cubierto, de lo contrario podría ser mejorado, tenemos $ 1/2 \ cdot | C | \ cdot f (x, y ^ *) $. De ello resulta que $$ \ frac {| C | -f (x, y ^ *)} {| C |} \ le \ frac {1} {2} $$ Así, el algoritmo voraz para un acoplamiento máximo es un algoritmo -approximatio de $ 1 / $ 2 por $ \ {mathsf Mínimo-cobertura de vértices} $. De ahí que $ \ {mathsf Mínimo-cobertura de vértices} $ es de $ 1 / $ 2 -approximable.

Desafortunadamente el error relativo no es siempre la mejor idea de la calidad de una aproximación como demuestra el siguiente ejemplo:

Ejemplo: Un simple codicioso-algoritmo puede aproximar $ \ mathsf {Mínimo-SetCover} $. Un análisis muestra que $$ \ frac {| C |} {| C ^ * |} \ le H_n \ le 1+ \ ln (n) y por lo tanto $$ $ \ {mathsf mínimo-SetCover} $ sería de $ \ frac {\ ln (n)} {1+ \ ln (n)} $ -. approximable

Si el error relativo es cerca de $ 1 $ la siguiente definición es ventajoso.

Vamos $ O = (X, L, M, opt) $ sea una optimización de problemas con $ f (x, y)> 0 $ para todos $ x \ in X $ y $ y \ en L (x) $ a $ y $ una aproximación-algoritmo para $ O $. La aproximación-proporción $ r_A (x) $ de solución factible $ A (x) = y \ in L (x) $ de la instancia $ x \ in X $ es $$ r_A (x) = \ begin {casos} 1 y F (x, A (x)) = f (x, y ^ *) \\\ max \ left \ { \ frac {f (x, a (x))} {f (x, y ^ *)}, \ frac {f (x, y ^ *)} {f (x, A (x))} \ right \ } & f (x, A (x)) \ ne f (x, y ^ *) \ end {casos} $$

Al igual que antes llamamos una aproximación algoritmo $ A $ un $ R $: Aproximación-algoritmo para la optimización de problemas $ O $ si el ratio de aproximación $ r_A (x) $ está delimitada por $ r \ ge1 $ para cada entrada $ x \ in X $. $$ r_A (x) \ le r $$ Y una vez más si tenemos un $ R $: Aproximación-algoritmo de $ A $ para la optimización de problemas $ O $ entonces $ O $ se llama $ r $ -approximable . Una vez más sólo nos importa el peor de los casos y definir el máxima aproximación del cociente $ r_A (n) $ para ser $$ r_A (n) = \ sup \ {r_A (x) \ mediados | x | \ le n \}. $$ De acuerdo con la relación de aproximación es mayor que $ 1 $ de soluciones subóptimas. Asímejores soluciones tienen proporciones más pequeñas. Por $ \ {mathsf mínimo-SetCover} $ Ahora podemos escribir que es $ (1+ \ ln (n)) $ - approximable. Y en caso de $ \ {mathsf mínimo-cobertura de vértices} $ sabemos del ejemplo anterior que es de $ 2 $ -approximable. Entre el error relativo y de relación aproximación tenemos relaciones simples: $$ r_A (x) = \ frac {1} {1- \ epsilon_A (x)} \ qquad \ epsilon_A (x) = 1- \ frac {1} {r_A (x)}. $$

Para pequeñas desviaciones de la $ óptima \ epsilon <1/2 $ y $ r <2 $ el error relativo es ventajoso sobre la relación de aproximación, que muestra sus puntos fuertes para grandes desviaciones $ \ epsilon \ ge media $ y $ r \ ge $ 2.

Las dos versiones de $ \ alpha $ -approximable no se superponen como una versión cuenta siempre $ \ alpha \ le 1 $ y el otro $ \ alpha \ GE 1 $. El caso $ \ alpha = 1 $ no es problemático ya que esto sólo se alcanza por medio de algoritmos que producen una solución exacta y en consecuencia no necesitan ser tratados como aproximación algoritmos.

Otra clase aparece a menudo APX . Se define como el conjunto de todos los problemas de optimización-$ O $ de $ $ NPO ese refugio de $ R $: Aproximación algoritmo con $ r \ ge1 $ que se ejecuta en tiempo polinómico.

Estamos casi a través. Nos gustaría copiar las ideas de éxito de reducciones y completitud de la teoría de la complejidad. La observación es que muchas decisiones NP-duro variantes de optimización-problemas se reducen a la otra mientras sus variantes de optimización tienen propiedades diferentes en cuanto a su approximability. Esto se debe a la polynomialtime-Karp de reducción utilizado en la reducción de NP-completitud, que no conserva la función objetivo. E incluso si las funciones objetivo se conserva la polynomialtime-Karp-reducción puede cambiar la calidad de la solución.

Lo que necesitamos es una versión más fuerte de la reducción, que no sólo los mapas de las instancias de la optimización de problemas $ O_1 $ a instancias de $ O_2 $, sino también buenas soluciones desde $ O_2 $ vuelta a buenas soluciones desde $ O_1 $.

Por lo tanto definimos el aproximación conservadora de reducción a dos de optimización-problems $ O_1 = (x_1, L_1, f_1, opt_1) $ y $ O_2 = (X_2, L_2, f_2, opt_2) $ de $ $ NPO. Llamamos a $ O_1 $ $ $ AP -reducible a $ $ O_2, escrito como $ O_1 \ le_ {AP} $ O_2, si hay dos funciones g $ $ y $ $ h y una constante C $ $ con:

1. $ g (x_1, r) \ en X_2 $ para todos $ x_1 \ en X_1 $ y racional $ r> 1 $
2. $ L_2 (g (x, r_1)) \ ne \ emptyset $ Si $ L_1 (x_1) \ ne \ emptyset $ para todos $ x_1 \ en X_1 $ y $ racional r> 1 $
3. $ h (x_1, y_2, r) \ en L_1 (x_1) $ para todos $ x_1 \ en X_1 $ y racional $ r> 1 $ por todas $ y_2 \ en L_2 (g (x_1, r)) $
4. Por $ fijo R $ ambas funciones $ g $ y $ h $ se puede calcular por dos algoritmos en tiempo polinómico en la longitud de sus entradas.
5. Tenemos $$ f_2 (g (x_1, r), y_2) \ le r \ Rightarrow f_1 (x_1, h (x_1, y_2, r)) \ le 1 + c \ cdot (r-1) $$ para todos $ x_1 \ en x_1 $ y racional $ r> 1 $ por todas $ y_2 \ en L_2 (g (x_1, r)) $

En esta definición $ g $ y $ h $ depende de la calidad de la solución $ r $. Así, por diferentes calidades las funciones pueden diferir. Esta generalidad no siempre es necesaria y acabamos de trabajo con $ g (x 1) y $ $ h (x 1, y_2) $.

Ahora que tenemos una noción de una reducción de la optimización a problemas por fin podemos transferir muchas cosas que sabemos de la teoría de la complejidad. Por ejemplo, si sabemos que O_2 $ \ $ en APX y mostramos que O_1 $ \ le_ {AP} $ O_2 se deduce que O_1 $ \ $ en APX también.

Finalmente podemos definir lo que entendemos por $ \ mathcal {C} $ - dura y $ \ mathcal {C} $ - completa para la optimización-problemas:

Sea $ O $ será una optimización-problema desde $ NPO $ y $ \ mathcal {C} $ a la clase de optimización a problemas de $ NPO $ entonces $ O $ se llama $ \ mathcal {C} $ -Hard con respecto a los $ \ le_ {AP} $ si para todo $ O '\ in \ mathcal {C} $ $ O' \ le_ {AP} O $ sostiene.

Así, una vez más tenemos una noción de un más duro problema en la clase. No es de extrañar un $ \ mathcal {C} $ - dura problema se llama $ \ mathcal {C} $ - con respecto a $ \ le_ {AP} $ si se trata de un elemento de$ \ Mathcal {C} $.

De este modo podemos ahora hablar de NPO $ $ $ -completness y APX $ -completness etc, y por supuesto que estamos ahora preguntamos a exhibir un primer NPO $ $ -Complete problema que asume el papel de $ \ {mathsf SAT PS Se trata casi de manera natural, que $ \ {mathsf ponderado satisfacibilidad} $ puede ser demostrado ser NPO $ $ -Complete. Con la ayuda del PCP-Teorema uno puede incluso demostrar que $ \ {mathsf Máximo-3SAT} $ es $ APX $ -Complete.

Answer 2

Por lo general, lo que se muestra es el NP-dureza de una versión "Gap" del problema. Por ejemplo, supongamos que quiere mostrar que es difícil CUBIERTA aproximado dentro de un factor de 2.

Se define la siguiente instancia "promesa" de juego de tapas que llamaremos 2-GAP-SET-COVER:

Fijar un número $ \ ell $. 2-GAP-SET-COVER consta de todas las instancias de la cubierta conjunto donde el tamaño de la cubierta de conjunto óptimo es o bien:

• como máximo $ \ ell $
• al menos $ un 2 \ ell $

Supongamos que se muestra que el problema de decidir cuál de los dos casos un problema cae en es NP-completo. A continuación, hemos demostrado que se aproxima CUBIERTA dentro de un factor de 2 es NP-difícil, porque podríamos utilizar tal algoritmo para distinguir estos dos casos.

Answer 3

Las dos respuestas existentes son muy informativo, pero no creo que ninguno de ellos realmente responde a la pregunta, que es: "¿Cómo puede un problema que no es ni siquiera un problema de decisión es NP-duro, cuando NP es una clase de los problemas de decisión? "

La respuesta es recordar lo que significa la NP-duros. Un problema $ L $ es NP-duro bajo algún tipo de reducciones si todos los problemas de NP puede ser reducido a $ L $. (Y $ L $ es NP-completo si es NP-duro y en NP.) De manera informal, NP-dura medios "Si pudiera resolver este problema, yo podría resolver todo en NP", incluso si el problema que está hablando no está en NP. NP-hard no requiere de miembros de la PN, sino que necesita la noción correcta de reducción.

Algunos ejemplos.

1. Cualquier NEXPTIME-problema completo $ L $ es NP-duro bajo en tiempo polinómico many-uno reducciones. Cualquier problema en NP está en NEXPTIME modo se puede reducir a $ L $ por definición. Por el teorema de la jerarquía temporal, $ L $ no puede estar en NP, por lo que $ L $ no es NP-completo.
2. #SAT es el problema de calcular el número de satisfacer las asignaciones a las fórmulas CNF. Está claro que no está en NP porque, como se observa, NP es una clase de problemas de decisión y #SAT no es uno de esos. Sin embargo, #SAT es NP-duro bajo las reducciones de Turing en tiempo polinómico, ya que podemos reducir el SAT a ella. Dada una instancia de SAT, nos preguntamos cuántas tareas satisfacer existen: si hay al menos uno, decimos "satisfiable"; de lo contrario, "unsatisfiable".
3. Let APPROXSAT sea el problema de calcular un número que está dentro de un factor de diez del número de asignaciones que satisfacen a una fórmula CNF $ \ phi $. Sólo para estar molesto, digamos que está permitido por ronda así, si $ \ phi $ tiene, digamos, tres tareas que cumplen, se permite que el algoritmo de pensar "0,3" y redondo que hasta cero. Esta es NP-duro bajo las reducciones de Turing en tiempo polinómico, porque todavía podemos reducir el SAT a ella. Dada una fórmula CNF $ \ phi $, pregunte por el número de asignaciones que satisfacen a $ \ varphi '= \ varphi \ wedge (Z_1 \ vee \ puntos \ vee Z_ {10}) $, donde el $ Z_I $ son nuevas variables. $ \ Phi '$ satisfiable es si, y sólo si, $ \ phi $ es, pero $ \ phi' $ es la garantía de tener más de 1.000 asignaciones que satisfacen, si tiene alguna. Por lo tanto, $ \ phi $ satisfiable es si, y sólo si, el algoritmo APPROXSAT dice que $ \ phi '$ tiene al menos 100 asignaciones satisfactorio.