Probar P = NP sin enunciados matemáticos / programa de computadora

Esta es mi primera publicación después de ser un usuario pasivo desde hace algún tiempo. Deseo hacer algunas preguntas si puedo. No soy matemático pero mi pregunta se relaciona con el campo de las matemáticas / informática. En particular, el problema P vs NP. Soy consciente de que este es un problema que los profesionales de élite aún no han podido resolver ...

De todos modos, me gustaría preguntar:

Si una persona que no es matemática ni programador elaborara un diagrama de flujo o una serie de pasos escritos en inglés básico que supuestamente proporciona una solución a uno de los problemas P vs NP, ¿eso se consideraría como 'prueba' de que P = NP .. para reclamar el premio Clays Institute :)? ¿O es imprescindible para uno escribir la solución como pruebas matemáticas / programa informático?

Gracias.

"No", puedes usar "inglés básico".

Si tuvo éxito, habría creado una prueba constructiva . Las pruebas en matemáticas a menudo son una mezcla de "inglés básico" como lo llamas y fórmulas matemáticas, pero no necesitan contener ninguna para ser una prueba válida.

Supongamos que tiene un diagrama de flujo de este tipo, lo que necesita probar, es decir, argumentar, es que su algoritmo funciona para cada instancia de problema. La forma en que lo haga depende completamente de usted, siempre y cuando la prueba no sea ambigua y todas las premisas que afirme hayan demostrado ser ciertas.

Una vez hecho eso, tienes una prueba matemática en tus manos. Entonces, realmente, debería haber dicho " Sí " al principio, necesitas una prueba matemática .

Hay que recordar que una máquina de Turing es una especie de diagrama de flujo. Así es la estructura de un programa de computadora en general. Por lo tanto, convertir "un diagrama de flujo" en una respuesta formal al problema debería ser bastante fácil, si realmente funcionó. De hecho, si uno comenzara con una respuesta terriblemente formal a P versus NP , la mayoría de los científicos informáticos tratarían de encontrar una formulación que se acercara lo más posible a una descripción sencilla en inglés para obtener una comprensión tan sólida de la solución como posible.

Pero hay un problema fundamental con el tipo de pregunta que estás haciendo. ¿Qué significa para alguien que sería capaz de resolver P versus NP , y al demostrar que son iguales, nada menos, que en realidad no sea ni un informático ni un matemático? Quizás no están empleados profesionalmente como informáticos o matemáticos, pero esto no viene al caso si tienen la habilidad de resolver lo que algunos (Scott Aaronson, por ejemplo) describen como el problema matemático más importante que jamás hayamos considerado. Si alguien tiene la capacitación (o incluso ha sido autodidacta) para abordar con éxito el problema y también para comunicar claramente la solución a los demás.al identificar las principales subrutinas y sus roles en la resolución, por ejemplo, SAT o HAMPATH, entonces si son empleados o incluso tienen títulos es un detalle irrelevante; Sin embargo, en ese caso son matemáticos o informáticos. Mejor aún si pueden describir cómo sus soluciones superan los obstáculos clásicos, como los resultados del oráculo, como los oráculos A para los cuales P ^A ≠ NP ^A (o lo contrario) al mostrar específicamente qué tipo de estructura en el problema se aprovecha el algoritmo, que no sería accesible en el modelo oracle. Sin embargo, el problema es que la mayoría de las personas que sueñan con resolver P versus NP como aficionados o extrañosparecen carecer de las habilidades de comunicación para describir realmente su trabajo adecuadamente, o (en virtud de no haber leído lo suficiente) desconocen los resultados que harían que su enfoque para resolver el problema estuviera condenado desde el principio.

Como con todos los sueños de gloria en estos días, hay un problema básico con la fantasía de ser el que resuelve P versus NP . El problema es que es casi imposible. En realidad no es imposible, o al menos no necesariamente imposible; solo casi así. Como alguien brillante con ambición, es posible que uno pierda de vista el hecho de que hay muchas otras personas brillantes: muchas de las cuales también han pensado en el problema; y muchos de los cuales son más brillantes que uno mismo, incluso por un par de órdenes de magnitud. Y que ha habido personas tan brillantes durante tanto tiempo como el problema ha existido; y, sin embargo, sigue sin resolverse. Sí, en principio es posible que todos lo piensen mal, y lo hayan estado haciendo durante décadas. Pero es esorealmente particularmente probable? Nadie debería esperar ser la única persona que puede detectar el único error de signo que todos los demás están cometiendo, porque si todos los demás están cometiendo ese error, entonces debe haber algo sobre el problema que llevará a uno a cometer el mismo error. O bien, en el caso más probable de que la razón por la cual el problema sigue sin resolverse no seaque las personas siguen cometiendo errores simples o aún no han pensado en el único truco que disuelve todo: lo que hace que el problema sea fundamentalmente difícil es esencialmente una dificultad objetiva del problema, y ​​ningún paso de baile inteligente le permitirá a uno simplemente bailar vals con gracia pasado todos los obstáculos; que lo que se requiere es un enfoque que no sea simplemente novedoso, sino bastante profundo, que identifique estructuras sutiles que no había una buena razón para que nadie haya visto antes. El tipo de estructura que es más probable que detecte al pensar continuamente sobre el problema durante años.

Si desea ser realista sobre lo que se necesitaría para resolver el problema P versus NP , puede compararlo con avances igualmente famosos en las últimas décadas, como las pruebas del teorema de los cuatro colores, el último teorema de Fermat o el Conjetura de Poincaré. Es posible que algún día tengan pruebas más simples, pero las pruebas originales lo llevan lejos en el desierto para llegar al final (o en el caso del teorema de los cuatro colores, la ruta es muy larga y repetitiva). No hay una razón particular para sospechar que P versus NP será diferente; para que si al final esresuelto por un aficionado, las posibilidades son extremadamente fuertes de que sea por alguien con conocimientos previos similares y conocimiento de las técnicas de alguien que está capacitado académicamente. Cualquier aficionado realista que sueñe con resolver P versus NP haría bien en tenerlo en cuenta.

Una prueba de que P = NP podría ser aceptado por una revista matemática, pero nunca será aceptado por los profesionales de élite. Las razones son que saben que P! = NP (al menos para todos los fines prácticos). También saben que es increíblemente difícil probar esto, por lo que incluso una prueba de que P! = NP será recibido con una buena cantidad de escepticismo por parte de los profesionales de élite.

Los profesionales de élite tienen razones más elaboradas que las que muchas mentes brillantes intentaron y no lograron construir un algoritmo polinomial para NP o probar N! = NP. Sin embargo, esperan razonablemente que este argumento sea el más convincente para un laico. Probablemente tengan razón en que la referencia a las barreras relacionadas con las pruebas relativizantes, las pruebas naturales o las pruebas algebrizantes rara vez son convincentes para un no experto. Si demasiados "aficionados" intentan resolver P vs NP de una determinada manera (por ejemplo, por resolución lógica o reduciéndolo a un problema de programación lineal), entonces alguien pasará por el dolor (esto a veces lleva años) para demostrar que Es probable que este ángulo de ataque específico esté condenado al fracaso.

Editar Estoy encantado de que esta respuesta siga atrayendo comentarios (negativos). Permítanme, por lo tanto, reemplazar la segunda parte de la respuesta (que parece no estar relacionada con los comentarios, pero puede distraer del punto principal) por la siguiente cita de Verdad vs Prueba :

Podríamos permanecer agnósticos, diciendo que simplemente no lo sabemos, pero puede haber demasiado escepticismo en la ciencia. Por ejemplo, Scott Aaronson una vez afirmó que en otras ciencias P! = NP ya se habría declarado una ley de la naturaleza. Tiendo a estar de acuerdo. Después de todo, estamos tratando de descubrir la verdad sobre la naturaleza de la computación y esta búsqueda no será más rápida si insistimos en descartar toda evidencia que no esté en forma de pruebas matemáticas de los primeros principios.

Este cambio no pretende reducir la cantidad de retroalimentación, sino dejar en claro que esta respuesta es seria sobre el hecho de que los expertos "saben que P! = NP", aun así no pueden probarlo.

23 nov 2013 Gracias nuevamente por todos los comentarios. Para el registro, la respuesta ahora tiene 7 votos a favor, 1 voto a favor y 14 comentarios (8 por mí). Debido a la cantidad de comentarios, las referencias interesantes y las justificaciones dadas en los comentarios están ocultas, así que decidí agregar algunas aquí:

• Como el mismo Gödel escribió a von Neumann, si P = NP fuera cierto "para todos los fines prácticos", entonces su teorema de incompletitud solo sería cierto en teoría, pero efectivamente falso en la práctica.

• En su artículo de 1971, Stephen Cook ... incapaz de producir contraejemplos para el procedimiento de Davis-Putnam (resuelto por Haken 1985). Hoy en día, muchas técnicas, resultados y contraejemplos están disponibles para "refutar" los solucionadores de NP eficientes propuestos. También P = NP contradice la "ley de conservación de la dificultad", la correspondencia "cualitativa infinitaria <-> cuantitativa finitaria", ...

• Hace mucho tiempo, Scott Aaronson escribió este comentario :

  anónimo: Usted afirma (como un hecho) que 3SAT es un lenguaje en NP que no puede calcularse en tiempo polinómico. Pero no puedes probarlo. ¿Es ese tu método científico? Si. Como firme creyente en la ciencia y la razón, me esfuerzo por distinguir claramente entre lo que puedo probar y lo que simplemente sé que es verdad.

• Scott es famoso por tratar de demostrar lo que significa que "sabe" algo, por ejemplo apostando $ 200,000: scottaaronson.com/blog/?p=458