¿Cómo no resolver P = NP?

Hay muchos intentos de probar o , y, naturalmente, muchas personas piensan en la pregunta y tienen ideas para probar cualquier dirección.P ≠ N $\mathsf{P} = \mathsf{NP}$$\mathsf{P} \neq \mathsf{NP}$

Sé que hay enfoques que han demostrado que no funcionan, y probablemente hay más que tienen un historial de fallas. También parece haber las llamadas barreras que muchos intentos de prueba no pueden superar.

Queremos evitar investigar los callejones sin salida, entonces, ¿qué son?

Diría que las barreras más conocidas para resolver son$P=NP$

1. Relativización (como lo menciona Ran G.)
2. Pruebas naturales: bajo ciertas suposiciones criptográficas, Rudich y Razborov demostraron que no podemos probar utilizando una clase de pruebas llamadas pruebas naturales.$P\neq NP$
3. Algebrización - por Scott Aaronson y Avi Wigderson. Prueban que las pruebas de que el álgebrizado no puede separar y N $P$$NP$

Otra con la que estoy familiarizado es el resultado de que ninguna formulación de LP puede resolver TSP (fue probado por Yannakakis para LP simétricos y recientemente se extendió a LP generales). Aquí hay una publicación de blog que discute el resultado.

Nota: Todavía no he revisado la respuesta cuidadosamente y hay partes que faltan por escribir, considérelo un primer borrador.

Esta respuesta está destinada principalmente a personas que no son investigadores en teoría de la complejidad o campos relacionados. Si eres un teórico de la complejidad y has leído la respuesta, avísame si notas algún problema o tienes una idea para mejorar la respuesta.

Donde puede encontrar soluciones reclamadas de P vs. NP

• Existe la página P-versus-NP que tiene una lista de tales afirmaciones.
• Los artículos que dicen resolver la pregunta se publican regularmente en arXiv .

Otras listas de cómo no resolver P vs. NP

Lance Fortnow, así que crees que te estableciste P verus NP , 2009

Scott Aaronson, Ocho señales de que una prueba reclamada de P imed NP es incorrecta , 2010

Página de Polymath para el artículo de Deolalikar , donde la sección de lecturas adicionales tiene una buena lista de referencias sobre el problema.

Cómo no acercarse a P vs. NP

Permítanme discutir "cómo no abordar P vs. NP" no en el sentido de ideas que no funcionarán, sino en un sentido más general. P vs. NP es un problema fácil de enunciar (ver también mi respuesta aquí ):

NP = P: Para cada problema de decisión con un algoritmo verificador de tiempo polinómico hay un algoritmo de tiempo polinómico.

o equivalente

Hay un algoritmo de tiempo polinómico para SAT.
SAT se puede reemplazar con cualquier otro problema NP-completo .

.

A menudo, las personas simplifican demasiado y filosofan demasiado el problema y exageran la importancia práctica del problema (como se indicó anteriormente). Tales afirmaciones a menudo tienen la intención de dar intuición, pero de ninguna manera reemplazan la afirmación matemática real del problema.

La eficiencia teórica no es lo mismo que la factibilidad en la práctica.

Permítanme primero con consecuencias prácticas exageradas.

I. ¡ Es posible que P = NP pero no ayuda para ningún problema en la práctica!

$2^{2^{64}} n^{65536} + 2^{2^{128}}$

$\neq$

$n^{\lg^*\lg^* n}$

$\lg^* n > 6$$2$

El punto principal aquí es que P es un modelo simple abstracto de computación eficiente, la complejidad del peor de los casos es un modelo simple abstracto de estimar el costo de un cómputo, etc. Todos estos son abstracciones, pero nadie en la práctica consideraría un algoritmo como el de (I) anterior como un algoritmo eficiente realmente. P es un buen modelo abstracto, tiene buenas propiedades, facilita los problemas técnicos y es útil. Sin embargo, como toda abstracción matemática, esconde detalles que en la práctica nos pueden interesar. Hay varios modelos más refinados, pero cuanto más complicado se vuelve el modelo, menos agradable sería discutir.

Lo que a la gente le importa en la práctica es calcular una respuesta al problema para los casos en que les importa usar una cantidad razonable de recursos. Hay tareas dependientes y deben tenerse en cuenta.

Intentar encontrar mejores algoritmos para casos prácticos de problemas NP-hard es un esfuerzo interesante y valioso. Existen algoritmos heurísticos para resolver SAT que se utilizan en la industria y pueden resolver casos prácticos de SAT con millones de variables. Incluso hay una competencia internacional SAT .

(Pero también hay pequeñas instancias concretas en las que todos estos algoritmos fallan y fallan bastante, en realidad podemos demostrar que todos los solucionadores de SAT modernos de última generación toman tiempo exponencial para resolver instancias simples como el Principio de casillero proposicional ).

Tenga en cuenta que la corrección y el tiempo de ejecución de los programas no se pueden obtener simplemente ejecutando el programa en instancias . No importa cuántas instancias intentes, ninguna cantidad es suficiente. Hay infinitas entradas posibles y debe mostrar la corrección y la eficiencia (es decir, el tiempo de ejecución es polinomial) del programa para todas ellas. En resumen, necesita una prueba matemática de corrección y eficiencia. Si no sabe qué es una prueba matemática, primero debe aprender algunas matemáticas básicas (lea un libro de texto de matemática discreta / teoría combinatoria / teoría de grafos, este es un buen tema para aprender sobre lo que se considera una prueba matemática).

También tenga cuidado con otras afirmaciones sobre P vs. NP y la consecuencia de sus respuestas. Tales afirmaciones a menudo se basan en simplificaciones similares.

¡Los teóricos de la complejidad realmente no se preocupan por una respuesta a P vs. NP!

Exageré un poco. Por supuesto que nos importa una respuesta a P vs. NP. Pero nos importa en un contexto. P vs. NP es nuestro problema principal, pero no es el objetivo final. Es un problema fácil de enunciar, involucra muchas ideas fundamentales, es útil para explicar el tipo de preguntas que nos interesan a las personas que no están familiarizadas con el tema. Pero no buscamos una respuesta Sí / No a la pregunta.

Buscamos una mejor comprensión de la naturaleza de la computación eficiente . Creemos que resolver la pregunta vendrá con tal comprensión y esa es la verdadera razón por la que nos preocupamos. Es parte de un gran cuerpo de investigación. Si desea tener una idea de lo que hacemos, eche un vistazo a un buen libro de texto de teoría de la complejidad, por ejemplo, " Teoría de la complejidad: un enfoque moderno " de Arora y Barak ( versión preliminar ).

$\neq$

En resumen, desde la perspectiva de un teórico de la complejidad.

P vs. NP no es un rompecabezas con una respuesta Sí / No. Buscamos una respuesta a P vs. NP porque creemos que llegará a una mejor comprensión de la naturaleza de la computación eficiente. Una respuesta sin un avance importante en nuestro entendimiento no es muy interesante.

Ha habido demasiadas ocasiones en que los no expertos han reclamado soluciones para P vs. NP, y esas afirmaciones generalmente sufren problemas que no habrían hecho si solo leyeran un libro de texto estándar sobre teoría de la complejidad.

Problemas comunes P = NP

Las afirmaciones de P = NP parecen ser más comunes. Creo que el siguiente es el tipo más común. Alguien tiene una idea y escribe un programa y lo prueba en algunas instancias y piensa que es tiempo polinómico y resuelve correctamente un problema de NP completo. Como expliqué anteriormente, ninguna cantidad de pruebas mostrará P = NP. P = NP necesita una prueba matemática , no solo un programa que parece resolver un problema de NP completo en tiempo polinómico.

Estos intentos suelen sufrir uno de los dos problemas:

I. el algoritmo no es realmente el tiempo polinomial.

II El algoritmo no resuelve todas las instancias correctamente.

$\neq$

[para ser escrito]

Cómo comprobar que su algoritmo realmente no funciona

No puede demostrar que su algoritmo funciona correctamente mediante pruebas. ¡Pero puedes demostrar que no funciona correctamente al probarlo! Así es como puede asegurarse de que su algoritmo no sea correcto si está dispuesto a hacer algún trabajo.

Primero, escriba un programa para convertir instancias de SAT (en el formato CNF estándar) al problema NP-hard que está resolviendo. SAT es uno de los problemas NP-hard más estudiados y las reducciones de otros problemas a SAT suelen ser fáciles. En segundo lugar, tome los ejemplos con los que luchan los solucionadores de SAT de última generación (por ejemplo, tome los ejemplos de la competencia SAT) y aliméntelos a su algoritmo y vea cómo funciona su algoritmo. Pruebe instancias difíciles conocidas como el Principio de Pigeonhole proposicional (y no haga trampas codificándolas como casos especiales), instancias criptográficas (como RSA Factoring Challenges ), instancias aleatorias k-SAT cerca del umbral , etc.

$10 n^2$

Cómo verificar su idea algorítmica P = NP no puede funcionar

Si hace esto, estará bastante seguro de que su algoritmo no funcionará (si funciona mejor que los solucionadores de SAT de última generación, compita en la próxima competencia y mucha gente estaría interesada en estudiar su algoritmo e ideas).

Ahora sabes que realmente no funciona, pero eso no es suficiente. Quieres saber por qué,

¿Cuál es la razón por la cual mi algoritmo no funciona? ¿Un problema pequeño que se puede solucionar o hay una razón fundamental por la que no puede funcionar?

A veces, el problema con el algoritmo es simple y uno puede identificar lo que estaba mal conceptualmente. El mejor resultado es que comprende la razón por la cual su idea no puede funcionar. A menudo no es el caso, su idea no funciona pero no puede entender por qué. En ese caso, tenga en cuenta:

¡comprender por qué alguna idea no puede funcionar puede ser más difícil que resolver P vs. NP!

Si puede formalizar su idea lo suficiente, podría probar una limitación de ideas particulares (por ejemplo, hay resultados que dicen que las formalizaciones particulares del algoritmo codicioso no pueden resolver los problemas de NP completo). Sin embargo, es aún más difícil y no tiene muchas posibilidades si no ha leído un libro de texto estándar de teoría de la complejidad.

En algún momento ni siquiera existe una idea conceptual clara de por qué el algoritmo debería funcionar, es decir, se basa en algunas heurísticas no bien entendidas . Si no tiene una idea conceptual clara de por qué su algoritmo debería funcionar, ¡entonces podría no tener muchas posibilidades de comprender por qué no funciona!

$\neq$

$\neq$

Problema 1: el autor no conoce la definición de P y NP, o peor aún, no entiende qué es una prueba matemática. Debido a que el autor carece de entrenamiento matemático básico, no comprende cuando se le dice que lo que está presentando no es una prueba (por ejemplo, los pasos no se siguen de los anteriores).

Problema 2: el autor confunde "no sabemos cómo" con "imposibilidad matemática". Por ejemplo, hacen varias suposiciones injustificadas y cuando se les pregunta "¿por qué esta afirmación es verdadera?" ellos responden "¿cómo puede ser falso?". Una de las más comunes es suponer que cualquier programa que resuelva el problema tiene que ir por pasos particulares, por ejemplo, tiene que calcular valores intermedios particulares, porque no puede pensar en una forma alternativa de resolver el problema.

[a completar]

$\neq$

[para ser escrito]

$\neq$

Si un reclamo no sufre estos problemas básicos, rechazarlo se vuelve más difícil. En el primer nivel se puede encontrar un paso incorrecto en el argumento. La respuesta típica del autor es que puedo arreglarlo y esto puede continuar. Similar a las soluciones P = NP, a menudo es muy difícil encontrar un problema fundamental con una idea que pueda demostrar que no puede funcionar, particularmente cuando la idea en sí misma es informal.

$\neq$

Quizás la técnica más común que no se puede usar es la relativización , es decir, tener una TM con acceso Oracle.

$A$$B$$\text{P}^A = \text{NP}^A$$\text{P}^B \ne \text{NP}^B$

$\text{P}\ne \text{NP}$$O$$\text{P}^O \ne \text{NP}^O$$A$

$\text{P} \stackrel{?}{=} \text{NP}$

Sugeriría leer esta publicación de blog de Lance Fortnow :

1. Entonces, usted piensa que se instaló P verus NP Está equivocado. Averígualo. A veces todavía puedes salvar algo interesante de tu prueba imperfecta.
2. Usted cree que la prueba es correcta. Tu creencia es incorrecta. Regrese al paso 1.
3. ¿Está haciendo suposiciones o atajos, incluso aparentemente pequeños y obvios? ¿Está utilizando palabras como "claramente", "obviamente", "fácil de ver", "debería", "debe" o "probablemente"? Afirmas que tal vez la pregunta más importante en todas las matemáticas sea resuelta. No puedes hacer suposiciones. Regrese al paso 1.
4. $n^k$
5. Envíe su trabajo a un archivo en línea. Tal vez algunas personas te digan lo que falta o está mal en tu trabajo. Esto debería llevarlo al paso 1. Pero en su lugar, realiza algunos cambios sin sentido en su papel y vuelve a publicar.
6. Eventualmente la gente ignora tu papel. Te preguntas por qué no estás obteniendo fama y fortuna.
7. Envías tu trabajo a una revista.
8. El papel es rechazado. Si eres inteligente, volverías al paso 1. Pero si fueras inteligente, nunca hubieras llegado al paso 7.
9. Usted se queja al editor de que el editor no comprende la prueba o que se puede arreglar fácilmente. Te sorprende que un editor o diario respetable trate tu trabajo de esta manera.
10. Vuelva a enviar el documento, apele, pruebe otras revistas, todo fue en vano.
11. Usted está convencido de que "el establecimiento" está suprimiendo su documento a propósito porque nuestro campo se volvería mucho menos interesante si solucionáramos el problema P versus NP, por lo que debemos mantenerlo abierto a toda costa.
12. Si te digo lo contrario, ¿me creerías?

Aquí hay un ángulo / referencia / giro algo oscuro / profundo / difícil / interno relacionado con los enfoques a través de circuitos que datan de la década de 1980 originalmente señalado por Luca Trevisan en otros lugares del ciberespacio, y también reiterado por Stasys Jukna, autor de un excelente referencia cercana al tema, Complejidad de la Función Booleana: Avances y Fronteras (Algoritmos y Combinatoria, Vol. 27 ).

Uno puede ver una tendencia anterior en algunos de los pensamientos de Razborov que eventualmente llevaron a las Pruebas Naturales (la llamada "naturalización"). ref [273] es muy técnico y difícil y no parece ser citado, desarrollado / expandido o reiterado mucho por documentos / libros posteriores, aunque Natural Proofs podría verse como una gran generalización posterior. el extracto es de John E Savages excelente referencia Modelos de computación p457

$\Omega(n^2)$$n$

[270] AA Razborov, "Límites inferiores en la complejidad monótona de algunas funciones booleanas", Dokl. Akad Nauk SSSR (Matemáticas soviéticas. Dokl.) 281 (1985), 798–801, (en ruso); Traducción al inglés en matemática soviética. Dokl 31 (1985), 354–357

[271] AA Razborov, "Un límite inferior en la complejidad de la red monótona del permanente lógico", Mat. Zametki 37 (1985), 887–900, (en ruso); Traducción al inglés en matemáticas. Notas 37 (6) (1985), 485–493.

[273] AA Razborov, "Sobre el método de aproximaciones", Proc. 21a Ann. ACM Symp. Theory of Computing (1989), 167-176.