Soy consciente de que esto parece una pregunta muy estúpida (o demasiado obvia para decir). Sin embargo, estoy confundido en algún momento.
Podemos mostrar que P NP si y solo si podemos diseñar un algoritmo que resuelva cualquier instancia dada de problema en NP en tiempo polinómico.
Sin embargo, no entiendo cómo demonios podemos probar que P NP . Por favor, discúlpeme por la siguiente similitud, ya que podría ser tan irrelevante, pero decirle a alguien que pruebe si P no es igual a NP me parece como decirle a alguien que pruebe que Dios no existe.
Hay una serie de problemas, que no pueden resolverse mediante un autómata finito no determinista (NFA) con un número polinómico de estados, independientemente de la tecnología actual (sé que esta es una definición descuidada). Además, tenemos un conjunto de algoritmos considerablemente grande que genera problemas de tiempo polinómico (ruta más corta, árbol de expansión mínimo e incluso suma de enteros ).
En resumen, mi pregunta: si creo que P NP , diría "¡entonces muestre su algoritmo que resuelve un problema de NP en tiempo polinómico!". Supongamos que creo P NP . Entonces, ¿qué preguntarías exactamente? ¿Qué quieres que te muestre?
La respuesta es claramente "su prueba". Sin embargo, ¿qué tipo de prueba muestra que un algoritmo no puede existir? (en este caso, un algoritmo de tiempo polinómico para un problema de NP )
fuente
Respuestas:
Hay tres formas principales que conozco que podrían probar que P NP≠ .
Mostrando que hay algún problema que está en NP , pero no en P . Probablemente esté familiarizado con la prueba de que la ordenación basada en la comparación necesita tiempo para ordenar una lista de elementos. En principio, se podría producir una prueba similar que muestre que 3SAT o algún otro problema completo de NP no se puede resolver en el tiempo para cualquier constante . La teoría de la complejidad geométrica busca utilizar herramientas de la geometría algebraica y la teoría de la representación grupal para probar tales límites inferiores, considerando las simetrías que poseen los problemas. La complejidad del circuito es otra.n O ( n c ) cΩ(nlogn) n O(nc) c
Mostrando que P y NP tienen diferentes propiedades estructurales. Por ejemplo, P se cierra bajo complementación. Si pudieras mostrar que NP co-NP≠ (es decir, que NP no está cerrado bajo complementación), entonces debe ser que P NP≠ . Por supuesto, esto solo está empujando el problema un nivel más profundo: ¿cómo probaría que NP co-NP≠ ?
Otra posibilidad es que sepamos que NP es exactamente la clase de problemas que se pueden definir en algo llamado lógica existencial de segundo orden. Si se pudiera mostrar que no hay una lógica que corresponda exactamente a P (o si hay una lógica pero es diferente a ), entonces P y NP deben ser diferentes. Una idea relacionada (de hecho, equivalente) es mostrar que P no tiene problemas completos en las reducciones definidas por la lógica de primer orden, ya que se sabe que NP sí tiene problemas completos en estas reducciones.∃SO
Demuestre que algún problema no es NP- completo. Si P NP= , entonces cada problema no trivial en NP es NP- completo bajo reducciones de tiempo múltiple polinomiales ("no trivial" aquí significa no o ). Entonces, si puede demostrar que algún problema en NP no es NP- completo, entonces debemos tener P NP .Σ ∗∅ Σ∗ ≠
fuente
No olvide que todavía tiene que demostrar que su algoritmo resuelve el problema y que se ejecuta en tiempo polinómico.
Primero, trate de explicar "por qué" P ≠ NP , y por qué esta razón puede usarse para probar P ≠ NP en un marco lógico adecuado. Luego dibuje una prueba y explique cómo se pueden defender sus partes más dudosas. A continuación, divida esta prueba en declaraciones más simples, que se pueden verificar de forma independiente.
También puede observar que hubo intentos de fortalecer los resultados con el tiempo. Los resultados iniciales para TSP solo se referían a la formulación de programación lineal simétrica, mientras que los últimos resultados no tienen esa restricción, y también se aplican al corte máximo y a los problemas de conjunto estable máximo además del TSP. Los resultados iniciales para la resolución consideraron solo los procedimientos básicos de resolución de Davis-Putnam y una sola clase de contraejemplos artificiales, mientras que los últimos resultados cubren grandes clases de métodos basados en la resolución y dan múltiples clases de contraejemplos que ocurren naturalmente.
Para TSP, no tengo idea de cómo se deben fortalecer aún más los resultados, excepto quizás aplicando más problemas además de TSP, corte máximo y conjunto estable máximo. Para resolverlo, tendría muchas ideas sobre cómo fortalecer aún más los resultados, pero el artículo al que me vinculé es de 2002, Stephen Cook y Phuong Nguyen publicaron una monografía Fundamentos lógicos de la complejidad de la prueba en 2010 que ni siquiera he examinado, y yo Supongo que ya cubrirá muchas de mis ideas. Es interesante observar la poca diferencia que realmente hace para la mayoría de nosotros cuánto se han fortalecido estos resultados con el tiempo, a pesar de nuestro interés en el P ≠ NPpregunta. Incluso si se hubiera demostrado mientras tanto que los algoritmos que dependen de sistemas lógicos sin un equivalente de la regla de corte no pueden resolver de manera eficiente los problemas de satisfacción, todavía creemos que esencialmente no ha habido progreso en P ≠ NP , que el problema es esencialmente sigue siendo tan abierto como siempre.
fuente