¿Por qué es importante demostrar que un problema es NP-completo?

¿Estoy en lo cierto al entender que probar un problema NP completo es un éxito de investigación? Si es así, ¿por qué?

Ali, buena pregunta.

Suponga que quiere mostrar que algún problema P es computacionalmente difícil. Ahora, podría conjeturar que P es difícil solo por el hecho de que todavía no tenemos algoritmos eficientes para ello. Pero esta es una evidencia bastante endeble, ¿no? Podría ser que nos hayamos perdido alguna forma agradable de ver P que haría que sea muy fácil de resolver. Entonces, para conjeturar que P es difícil, querríamos acumular más evidencia. ¡Las reducciones proporcionan una herramienta para hacer exactamente eso! Si podemos reducir algún otro problema natural de Q a P, entonces hemos demostrado que P es al menos tan difícil como Q. Pero Q podría ser un problema de un área matemática completamente diferente, y las personas pueden haber luchado durante décadas para resolver Q también . Por lo tanto, podemos ver nuestro fracaso para encontrar un algoritmo eficiente para que Q sea evidencia de que P es difícil. Si tenemos muchos de esos Q '

Esto es exactamente lo que proporciona la teoría de la integridad de NP. Si demuestra que su problema es NP-completo, entonces ha vinculado su dureza a la dureza de cientos de otros problemas, cada uno de interés significativo para varias comunidades. Por lo tanto, moralmente hablando, puede estar seguro de que su problema es realmente difícil.

Probar un problema NP-Complete es un éxito de investigación porque le libera de tener que buscar una solución eficiente y exacta para el problema general que está estudiando. Demuestra que su problema es miembro de una clase de problemas tan difícil que nadie ha podido encontrar un algoritmo eficiente y exacto para ninguno de los problemas, y tal solución para cualquiera de los problemas implicaría una solución para todos los problemas. problemas.

Por lo general, es un trampolín, porque su problema aún está ahí, simplemente tiene que relajar sus necesidades. Por lo general, las personas intentan descubrir cómo relajar uno o más de "eficiente", "exacto" o "general". Ineficiente-y-exacto-y-general es el intento de encontrar constantes cada vez mejores en el exponente de estos algoritmos. Eficiente e inexacto y general es el estudio de algoritmos de aproximación. Eficiente y exacto, pero no general, es el estudio de la trazabilidad de parámetros fijos y la búsqueda de subclases de entrada para los que se pueden encontrar algoritmos eficientes.

Veamos dos casos diferentes por los que a dos personas diferentes les gustaría probar un problema :$NP-complete$

a) Estás trabajando en un proyecto de software. Una vez que haya especificado su sistema, está comenzando a definir la arquitectura de su aplicación. Esto incluye desglosar el gran problema / necesidad que la aplicación sirve para problemas más pequeños. Digamos que se le ha asignado la tarea de encontrar un algoritmo eficiente (¡no queremos que nuestra aplicación sea lenta!) Para uno de esos problemas más pequeños. Después de luchar por un tiempo, no puedes encontrar un algoritmo polinómico. Entonces podría pensar: tal vez este problema es muy difícil, por lo que es muy difícil (o incluso imposible) encontrar un algoritmo eficiente. Al demostrar que el problema es , tiene alguna evidencia de esta conjetura suya y debe comenzar a considerar un enfoque alternativo (por ejemplo, alterar el problema para que sea más fácil).$NP-complete$

b) Estás investigando la teoría de la complejidad. Por definición, desea caracterizar los problemas (o clases de problemas) de acuerdo con la cantidad de recursos necesarios, es decir, la dificultad para resolverlos. Al demostrar que cierto problema es , obtienes algunas ideas:$NP-complete$

i) Sabes que tienes un vasto conocimiento del problema. En lugar de trabajar en un solo problema, puede trabajar con la clase de , lo que podría llevarlo a nuevas ideas.$NP-complete$

ii) Se permiten investigaciones que quieran probar otra forma de hacerlo. Tal vez su problema sea más fácil de atacar que .3 - S A $P=NP$$3-SAT$

iii) En la dirección inversa, puede utilizar su nuevo problema como representante de . Al estudiarlo, tal vez puedas entender por qué este problema es tan difícil de resolver (= no tiene un algoritmo eficiente) y aplicar este conocimiento a todos los demás problemas de la clase. (eso es lo que Deolalikar intentó hacer con el problema de )C L I Q U $NP-complete$$CLIQUE$

Resumiendo, caracterizar un problema le permite utilizar técnicas comunes. Al estudiar la clase con la que está relacionada, puede pensar en un nivel abstracto, sin preocuparse por los detalles de este problema en particular, que es común en matemáticas y ciencias en general. Trabajar con clases en lugar de miembros individuales le permite utilizar técnicas conocidas y, además, aplicar sus conocimientos a un mayor número de objetos, en lugar de solo uno.

Cada problema tiene varias conexiones con otros problemas. Además, existen relaciones entre un problema y las clases de complejidad.

Por lo tanto, clasificar un problema como NPC generalmente nos da una idea de otros problemas, así como de las clases de complejidad.

Por ejemplo, tome el problema del isomorfismo gráfico (GI). En el siguiente artículo:

Uwe Schöning, El isomorfismo gráfico está en la jerarquía baja , Actas del 4º Simposio anual sobre aspectos teóricos de la informática , 1987, 114–124; también: Journal of Computer and System Sciences, vol. 37 (1988), 312–323.

está comprobado que si GI ∈ NPC, entonces la jerarquía polinómica (PH) colapsa a su segundo nivel; que será un gran avance en la teoría de la complejidad estructural.

$p$$p$$p$$p$