Informática teórica: ¿cómo empiezo a resolver el problema P = NP?

Para resolver este problema, primero debe saber mucho sobre teoría de la complejidad y muchas matemáticas. Tendría que internalizar las barreras existentes conocidas para el problema, incluida la relativización, las pruebas naturales y la algebrización. Un curso básico en teoría de la complejidad cubre la relativización y las pruebas naturales, y la algebrización se discute aquí: http://www.scottaaronson.com/pap… .

Debe estar claro para usted en este punto que 1. hay resultados mucho más fáciles en la teoría de la complejidad que tampoco podemos probar, y 2. las barreras existentes para una prueba no son las únicas barreras.

Su idea sobre los “primitivos” es cierta en la superficie, pero en matemáticas rara vez se sabe de antemano qué primitivos serán necesarios para resolver un problema (aunque puede tener algunas corazonadas). Por lo general, es mejor venir armado con la mayor variedad de herramientas posible. Tenga en cuenta que PvsNP puede expresarse como un problema puramente combinatorio. Hablando de eso, el combinatorio Tim Gowers publicó algunas conferencias introductorias de teoría de la complejidad desde su punto de vista: http://sms.cam.ac.uk/collection/… .

El enfoque de GCT http: //ramakrishnadas.cs.uchicag … es interesante porque 1. se basa en algunas herramientas poderosas (geometría algebraica y teoría de la representación), y 2. Mulmuley argumenta explícitamente qué cree que es la barrera “más grande” para prueba, y ha hecho el trabajo preliminar para demostrar que su enfoque propuesto tendrá la capacidad básica de superar esa barrera.

Nota al pie: Me gustaría agregar el siguiente conocimiento. Es decir, no es necesario probar P vs NP para que el problema tenga un impacto en su vida. La teoría de la complejidad formaliza las relaciones (computacionales) entre problemas matemáticos y cotidianos. Estas interconexiones con frecuencia son intuitivamente aparentes de alguna manera para quienes trabajan en los problemas. La teoría de la complejidad proporciona el marco para dar sentido a tales intuiciones, y de ese modo ofrece un servicio valioso para aquellos que estén interesados.

No estoy seguro de por qué me preguntan esto, ya que no soy un científico de la computación, pero como mínimo probablemente quieras

1. tiene un buen conjunto de ejemplos para probar: problemas que se sabe que están en P, que se sabe que están en NP, que se sabe que están completos en NP y que se sabe que están fuera de P.
2. entienda los teoremas relevantes de no ir, por ejemplo, Razborov-Rudich, para que no pierda su tiempo en un callejón sin salida conocido.

Como un enfoque general para este tipo de problema, generalmente busco en Google algo así como “plan de estudios razborov rudich”, para encontrar un curso que cubra el tipo de material que quiero aprender. Encontré lo siguiente:

Programa para la teoría de la complejidad computacional WiSe 13/12

Luego encontraría la descripción de ese curso en el catálogo de la universidad, rastrearía los requisitos previos hasta que encontrara uno en un nivel con el que ya me sintiera cómodo, y proceda a partir de ahí usando eso como un mapa. Después de trabajar con el equivalente a un año de clases (ya sea tomándolas en persona, leyendo libros, viendo videos en línea o lo que sea), tal vez estaría en una mejor posición para evaluar el camino a seguir. En el peor de los casos, siempre podría seguir el mapa que hice.

En la actualidad no tenemos ningún método para mostrar si [matemática] P = NP [/ matemática] o [matemática] P \ neq NP [/ matemática], de lo contrario ya lo habríamos mostrado. Supongo que te refieres a estudiar el problema, no a resolverlo. Otros han dado buenas referencias. Otro enfoque para observar que los informáticos teóricos tienen estudios es el concepto de dureza de aproximación y el teorema de PCP (que en sí mismo puede tener cursos completos dedicados a ello).

Abordar todo el problema, tal como está, es obviamente el enfoque equivocado. El método estándar es transformar los problemas irresolubles en problemas solucionables. El último Theorum de Fermat no se resolvió estudiando la ecuación, se resolvió estudiando muy diferentes tipos de problemas, conectando los diferentes tipos de problemas y demostrando el resultado equilibrado.

Comenzaría mirando las diferentes clases de problemas por complejidad de tiempo y la jerarquía que forman. La complejidad del tiempo es probablemente el dominio incorrecto para trabajar, por lo que debe poder transformar el dominio en uno que sea útil. No hay escasez, su único requisito es que realmente debería ayudar. Su transformación tiene que producir una respuesta decisiva. No tiene sentido transformar la notación O grande en, digamos, topología si luego dice “por lo tanto P = NP si y solo si una morsa de merengue de limón podría comer el cuarto toro de la izquierda”, eso simplemente reemplaza un problema con otro.

Puede tener diferentes clases de razón para diferentes clases de problema NP. Tiene derecho a prefijar con “para no”, “para uno o más” o “para todos”. Lo que no puede hacer es sufijo con “quizás”.

Obtendría una visión general de la teoría de la complejidad, pero la respuesta no está allí y no vale la pena mirarla. Sin embargo, debes saber lo que estás transformando. Realmente saben. Hay siete u ocho ramas principales de las matemáticas y no tienes idea de cuál tendrá la respuesta. Por lo tanto, debes dominarlos a todos. Debes ser un archimago de las matemáticas, para hacer algo como esto con una sola mano.

Se puede hacer. Muchos polymaths han dominado más de siete temas y estos están estrechamente entrelazados, lo que lo hace más fácil. Esperaría que tome más de 35 años y, si eres sensato, utilizarás la educación superior para certificar lo que sabes. Debería poder manejar dos, quizás tres, doctorados fuera de él.

En ese momento, tendrá que pagar tarifas de millones de dólares para hablar en conferencias. Un Gran Maestro Matemático, posiblemente el primero en la historia del sujeto, un contendiente por el Récord Mundial Guinness en certificaciones y un portavoz de al menos una bebida con cafeína.

Esto significa que estará perfectamente ubicado para aturdir al mundo con la respuesta en su discurso de jubilación. Para entonces, el premio y la medalla de campo serán papas pequeñas en cuanto a dinero en efectivo, pero se verán geniales en el manto de su mansión de Beverley Hills.

Trabajo real: no, no tendrás tiempo para eso. Después de los requisitos educativos, solo le quedará tiempo para el problema. Tu fortuna dependerá de ser la versión académica de Paris Hilton en lugar de la versión matemática de Seymour Cray.

Habrá algunos problemas en el departamento de préstamos, por lo que tendrá que persuadir a sus amigos para que descubran tesoros piratas ocultos y galones hundidos para financiar su trabajo. O persuadir al gobierno de que la educación es una obligación de un gobierno avanzado para una nación avanzada. Creo que es mejor apegarse al oro pirata.

Opcion A:
Comienza por rendirse y encontrar un mejor uso de su tiempo.

Opcion B:

1. Mire una descripción del problema (proporcionada en una publicación anterior). Realmente trata de entenderlo.
2. Tome Mathematics for Computer Science para aprender a escribir correctamente una prueba. Pueden surgir ideas sobre cómo resolver el P = NP.
3. Acércate al problema.
4. Confundirse e ignorar su entrenamiento en el paso 2 y escribir una prueba incorrecta.
5. Haga que su prueba sea confirmada como incorrecta por profesores y colegas.
6. Tenga en cuenta que su comprobante no funciona en todos los casos, y solo utilizó un ejemplo, como Vendedor ambulante.
7. Lo intentas con otros problemas. Recuerdas tristemente que esto tiene que funcionar para todos los casos. Todos ellos: cada problema concebible … que se haya hecho. Para empezar, vea si puede romper el RSA en tiempo polinómico. Incluso si lo hiciera, ¿su solución funcionará igual de bien para otros problemas? No hay almuerzo gratis amigo, no hay almuerzo gratis.
8. Tenga en cuenta que la única forma lógica de resolver P = NP para un número infinito de casos es si puede tomar el tiempo polinómico invariante y convertirlo en una variante / manipularlo … lo que actualmente está fuera del alcance de la comprensión humana.
9. Cuando reconoce que requiere manipulación del tiempo, se pone en contacto con los físicos que están investigando eso (conozca al físico que quiere construir una máquina del tiempo para comunicarse con su padre muerto). O pasa a un esfuerzo más útil que podría lograrse en toda tu vida y aún te traen admiración y gloria. Como convertirse en el mejor jugador de banjo del mundo o acabar con el hambre del mundo con Soylent – Free Your Body.
10. Vive una vida feliz, ya sea buscando algo más o dejando la investigación a tiempo para aquellos expertos en la materia que ya están avanzando en su comprensión.

Aunque prácticamente solo trabajo en problemas de sistemas complejos, solo tengo una comprensión superficial del problema tal como lo plantea la comunidad TCS.

Sin embargo, dada la historia de este problema y la cantidad de personas muy inteligentes que trabajan en el problema, es seguro decir que NO encontrará la respuesta ante esta comunidad siguiendo lo que la comunidad está haciendo. ¡Simplemente tienen demasiado ventaja!

La única esperanza de resolver el problema (antes que otra persona) es hacer algo diferente. Esto puede sonar obvio pero también es profundo.

Una pista: la solución a cada problema está limitada por dos lados: sobre abstracción en uno y sobre especialización en el otro.

Pequeño aporte: No es que te esté desanimando. Pero entienda que el mundo de TCS está lleno de personas extremadamente inteligentes. Siempre lo ha sido, y (creo) siempre lo será. Y no tienen nada hasta ahora. Así que creo que será un viaje muy duro.

Se puede adaptar el siguiente enfoque:

Estoy tratando de formar un grupo en línea para resolver P = NP al encontrar algoritmos polinómicos para la satisfacción lógica (SAT), una piedra angular para las aplicaciones de inteligencia artificial. Tengo el presentimiento de que P = NP en realidad se puede probar.

Se sabe que en esta cadena de inclusiones:
[matemáticas] P \ subseteq NP \ subseteq PSPACE \ subseteq EXPTIME [/ math]
al menos una inclusión es adecuada (es decir, la igualdad no se cumple), según el “teorema determinista de la jerarquía temporal”. Aparte de eso, ninguna de las inclusiones ha demostrado ser adecuada hasta ahora. Tenga en cuenta que este teorema se prueba mediante la diagonalización , es decir, el teorema de Cantor de que la cardinalidad de un conjunto de potencia debe ser mayor que la cardinalidad del conjunto mismo. En otras palabras, la prueba se basa en la cardinalidad . Pero (con mi conocimiento limitado y diciendo esto vagamente) no he conocido pruebas de cardinalidad similares que sean “más pequeñas” que las de Cantor. ¿Significa que solo hay 1 desigualdad dentro de esa cadena?

Mi primera idea fue trasladar el problema de una configuración discreta a una configuración “uniforme”, inspirada en el método de punto interior de tiempo polinómico de Karmarkar para la programación lineal. Pero resultó ser un callejón sin salida, al menos desde mi perspectiva actual. Una exposición de este hilo está en “P = NP, mi primera puñalada al problema”.

Deseo comenzar un grupo de voluntarios para compartir ideas, técnicas, etc., para resolver el problema en línea y en colaboración. ¿Alguien interesado?

PD: algunos libros que encuentro útiles son:

• “La naturaleza de la computación” de Moore & Mertens 2011 es una buena introducción a P = NP. Aunque aprendí el material de otras fuentes antes de ver ese libro.
• Para la relajación del SAT a la programación lineal, una buena referencia inicial es el libro de Chandru y Hooker “Métodos de optimización para la inferencia lógica” (1999).
• Manual de SATisfiability, 2009.

No aconsejaré a nadie que dedique su tiempo a esto, especialmente si quieres hacerlo por el millón de dólares que se ofrece o por fama, o lo que sea. Probablemente hay formas más eficientes de lograr estos objetivos.

De todos modos, si necesita algunas ideas descabelladas, diré que mire el problema de los 3 cuerpos en física. El problema de 2 cuerpos es tan fácil de analizar, mientras que el de 3 cuerpos es casi imposible y, como dijo Newton:

Debido a la desviación del Sol del centro de gravedad, la fuerza centrípeta no siempre tiende a ese centro inmóvil y, por lo tanto, los planetas no se mueven exactamente en elipses ni giran dos veces en la misma órbita. Cada vez que un planeta gira, traza una nueva órbita, como en el movimiento de la Luna, y cada órbita depende de los movimientos combinados de todos los planetas, sin mencionar la acción de todos estos. Pero considerar simultáneamente todas estas causas de movimiento y definir estos movimientos mediante leyes exactas que admiten un cálculo fácil excede, si no me equivoco, la fuerza de cualquier mente humana.

Por supuesto, hay una razón muy bien comprendida de por qué el problema de los 3 cuerpos es difícil de analizar (como lo demostraron Henri Poincare y Ernst Bruns en 1887).

Estoy seguro de que probablemente haya oído hablar de 2-SAT y 3-SAT y probablemente sepa que 3-SAT es NP-Complete.

Esta puede ser una opinión algo no convencional, pero puede haber algo más que un parecido pasajero entre el 2 vs 3 – SAT y el problema del cuerpo 2 vs 3.

El problema del cuerpo 2 contra 3 parece ser un análogo físico de un problema computacional profundo. Por supuesto, no tengo forma de probar esto, pero creo que es algo interesante para explorar.

Y finalmente, en caso de que te lo estés preguntando, ¡NO estoy trabajando en el problema P vs NP! 🙂

Le recomiendo que lea la siguiente publicación de blog de Gowers: ¿Cómo no probar que P no es igual a NP?