Todos los problemas NP se reducen a problemas NP completos: entonces, ¿cómo pueden los problemas NP no ser NP completos?

10

Mi libro dice esto

  • Si un problema de decisión B está en P y A se reduce a B, entonces el problema de decisión A está en P.
  • Un problema de decisión B es NP completo si B está en NP y para cada problema en A en NP, A se reduce a B.
  • Un problema de decisión C es NP completo si C está en NP y para algunos problemas B de NP completo, B se reduce a C.

Entonces mis preguntas son

  1. Si B o C está en NP completo, y todos los problemas en NP se reducen a un problema de NP completo, utilizando la primera regla, ¿cómo puede cualquier problema de NP no ser NP completo?
  2. Si A se reduce a B, ¿B se reduce a A?
complexity-theory np-complete decision-problem rubixibuc
fuente
2
Dato interesante relacionado con su n. ° 1: si P no es igual a NP, sabemos que debe haber problemas de NP que no sean NP completos (esto se llama teorema de Ladner. Ver NP Intermedio ). Lo extraño es que no estamos seguros de ningún problema de cálculo común que se ajuste a esta categoría. El problema utilizado en el teorema de Ladner se construye artificialmente para probar el teorema, pero es prácticamente irrelevante.
Lucas Cook
44
@Lucas, Factoring y GraphIso se conjeturan como NPI, también vea esto .
Kaveh
@Kaveh: Buena lista de candidatos NPI, ¡gracias! Para aclarar, estaba diciendo que no estamos "seguros" de un problema natural de NPI con la misma certeza que los problemas de Ladner. Es decir, si , los únicos problemas de NPI conocidos con certeza son los artificiales relacionados con la jerarquía de Ladner. PAGS≠nortePAGS
Lucas Cook

Respuestas:

13

Si A se reduce a B, ¿B se reduce a A?

No. Para un ejemplo realmente inventado, cualquier posible problema computable A es reducible al problema de detención: simplemente pase como entrada el algoritmo que resuelve el problema A pero con un while(true)tack al final después del caso verdadero o falso. Sin embargo, sabemos que el problema de detención no es computable, por lo que no puede reducirse a ningún algoritmo A.

La idea básica es que si hay una reducción de A a B, puede aprender que B es al menos tan difícil de resolver como A y requiere un algoritmo que sea al menos igual de poderoso.

Entonces, si un problema A se reduce a un problema fácil B, entonces podemos deducir que A es fácil (ya que la reducción nos da el algoritmo eficiente) y si un problema difícil A se reduce a un problema B, podemos deducir que B también es difícil ( ya que si B fuera fácil, entonces A también debería ser fácil). Sin embargo, todavía existe la posibilidad de hacer una reducción tonta de un problema fácil a un problema difícil, pero en este caso no podemos deducir ninguna conclusión.

hugomg
fuente
8

Si B o C está en NP Completo, y todos los problemas en NP se reducen a un problema de NP Completo, usando la primera regla, ¿cómo puede cualquier problema de NP no ser NP completo?

La primera regla es sobre problemas en P. No tiene nada que ver con la integridad de NP. Si el problema A es NP Completo y el problema B se reduce a A, eso no significa que B sea NP Completo.

Si A se reduce a B, ¿B se reduce a A?

Generalmente no, no.

sepp2k
fuente
"No en general, no", ¿por qué? Un poco de explicación también podría ser útil para los novatos. También se debe proporcionar una explicación para su primera respuesta.
nbro
-1

Solo tengo la idea básica sobre los problemas de NPC y NP. Pero todo lo que quiero comentar es sobre "¿Si A se reduce a B, entonces B se reduce a A?"

Simplemente considere un conjunto A que tenga {2,3,4,5} elementos y el conjunto B que tenga {3,4}. Entonces, A puede reducirse a B. Pero B no puede reducirse a A. En cambio, B puede expandirse a A si B gana {2,5} elementos.

Pero si A y B están teniendo lo mismo. entonces A puede reducirse a B o B puede reducirse a A.

Naveen CS
fuente
Esta no es la idea correcta de reducción. La reducción no se trata de que los conjuntos ganen o pierdan elementos. Más bien, se trata de poder convertir una instancia de un problema en otro usando una máquina / algoritmo de Turing.
jmite
Okay. Entonces, si algún problema se reduce a otro usando algún algoritmo, entonces no es posible recuperar el problema de la salida reducida usando ese mismo algoritmo nuevamente.
Naveen CS
1
No estoy totalmente seguro de lo que quieres decir, pero creo que no es posible. Si no me equivoco, estas reducciones pueden ser muchas a una. A se reduce a B si un número polinómico de llamadas a una subrutina que resuelve B permite que A se resuelva en tiempo polinómico. Diferentes instancias de A podrían invocar una llamada a la misma instancia de B.
jmite
2
La pregunta es sobre problemas de decisión, no sobre conjuntos. ¿Cómo es útil mirar conjuntos? Usar la palabra "reducido" para significar que un conjunto es un superconjunto de otro ni siquiera es una terminología común.
Gilles 'SO- deja de ser malvado'