¿Por qué es necesariamente relevante "P frente a NP"?

Question

Quiero empezar dando dos ejemplos:

1) El problema de Graham es decidir si una determinada coloración de aristas (con dos colores) del grafo completo en vértices $\lbrace-1,+1\rbrace^n$ contiene un plano $K_4$ coloreado con un solo color. El resultado de Graham es que tal $K_4$ existe siempre que $n$ es suficientemente grande, mayor que algún número entero $N$ .

Hace poco me enteré de que el número entero $N$ determinado por el problema de Graham se sabe que se encuentra entre $13$ y $F^{7}(12)$ que se llama El número de Graham una cifra que supera cualquier imaginación y que según Wikipedia es prácticamente incomprensible . Algunos consideran que es el mayor número que se ha utilizado nunca en un argumento matemático serio.

Una forma de verlo es la siguiente: El problema de Graham de decidir si para un determinado $n$ y dada la coloración tal planar $K_4$ existe toma tiempo constante . En efecto, si $n$ es pequeño tienes que mirar, si $n$ es grande, ya está. Sin embargo, esto lleva un tiempo polinomial (comprobar las cuatro parejas de vértices) a todos los efectos prácticos (suponiendo que $N$ se acerca a su límite superior).

Estoy seguro de que alguien puede inventar un algoritmo que requiera un tiempo exponencial a efectos prácticos, pero constante o polinómico en general.

2) También aprendí que la mejor prueba de Lema de regularidad de Szemerédi da un límite a un cierto número entero $n(\varepsilon)$ que es el $\log(1/\varepsilon^5)$ -iteración de la función exponencial aplicada a $1$ . Este límite parece ridículo en el sentido de que ni siquiera permite aplicaciones interesantes de este resultado (digamos con $\varepsilon=10^{-6}$ ) a redes como Internet, redes neuronales o incluso cualquier cosa prácticamente imaginable. En este punto, esto es sólo un límite superior, pero Timothy Gowers demostró que $\log(1/\varepsilon)$ -son necesarias iteraciones.

Una vez más, parece que uno podría cocinar problemas algorítmicos razonables que tienen soluciones que son de tiempo polinómico, pero prácticamente inútil. Quizá se pueda hacer algo mejor en casos concretos, pero para ello se necesitan datos adicionales.

---

Acercándonos a la pregunta, ¿qué pasaría si finalmente $P=NP$ pero la prueba implica algo así como la existencia de una solución al problema de Graham o una aplicación del lema de regularidad de Szemerédi, de modo que finalmente los límites del algoritmo de tiempo polinómico son por alguna razón tan pobres que nadie quiere siquiera construirlo explícitamente. Quizá los límites sean exponenciales a todos los efectos prácticos, pero aún así polinómicos.

A menudo he oído el argumento de que, una vez encontrada una solución polinómica para un problema razonable, la investigación posterior también ha producido algoritmos de tiempo polinómico practicables. Al menos para el problema de Graham esto parece fallar miserablemente hasta ahora.

Pregunta: ¿Existe alguna prueba teórica de ello?

Ahora, tal vez un poco provocativo:

Pregunta: ¿Por qué pensamos que $P\neq NP$ ¿es necesariamente importante?

Sé que $P$ vs. $NP$ es importante por razones teóricas y conceptuales, pero ¿y si finalmente $P=NP$ se mantiene, pero no se puede encontrar ninguna prueba efectiva. Supongo que esto no cambiaría mucho.

EDITAR: Para que quede claro: no descarto en absoluto la teoría de la complejidad y puedo apreciar los resultados teóricos, aunque no tengan ninguna utilidad práctica.

Answer 1

Si $P = NP$ es al fin y al cabo sólo una información; además, la gente espera que no sean iguales. Lo mismo puede decirse de cualquiera de los problemas del Premio Clay. Entonces, ¿qué sentido tiene? Puesto que es una suposición muy común que $P \ne NP$ Como la conjetura de Poincaré se ha demostrado en muchos artículos importantes de informática y matemáticas, la gente espera que la demostración sea también muy interesante y que haya mucho que aprender de ella. Al fin y al cabo, cada vez que se ha demostrado alguna versión de la conjetura de Poincaré (por Smale, Freedman, Perelman, o incluso en 2D por Riemann et al) o se ha refutado (por Milnor en el caso suave en altas dimensiones), la demostración ha dado lugar a todo tipo de otras matemáticas interesantes. De vez en cuando, las matemáticas son un poco crueles y una demostración largamente esperada no resulta tan interesante como se esperaba. Posiblemente la primera prueba de la trascendencia de $\pi$ fue un ejemplo de ello. Pero no es lo que suele ocurrir.

En el caso concreto del $P$ vs $NP$ problema, es fácil ver algunas de las cuestiones relacionadas que, con suerte, se verían afectadas. Se puede bajar por la lista de problemas NP-duros y preguntar, con más precisión, cómo de difícil es cada uno. Las reducciones entre estos problemas le dicen que son aproximadamente tan difíciles unos como otros, pero eso es todo. Además, hay muchas otras separaciones conjeturadas entre clases de complejidad que parecen similares a $P$ vs $NP$ . $P$ vs $PSPACE$ parece similar, pero estos dos deberían estar mucho más separados. $P$ vs $BQP$ es una pregunta especialmente jugosa, ya que ni siquiera es obvio para todo el mundo (aunque creo que es una apuesta segura) que merezca la pena construir un ordenador cuántico.

Y lo que es mejor, los resultados dan la vuelta a la tortilla. Dada una suposición que no es mucho más fuerte que $P \ne NP$ se deduce que $P = BPP$ es decir, todo algoritmo aleatorio de tiempo polinómico puede ser desaleatorizado en tiempo polinómico.

Sí, es posible que las matemáticas sean crueles y resulte que 3-SAT se puede resolver en tiempo $O(n^G)$ donde $G$ es el número de Graham. ¿Pero por qué debería serlo? Digamos que nuestra estética y nuestra intuición para esperar una prueba muy influyente son buenas el 90% de las veces. Recientemente nuestra media de bateo ha sido algo así. Es razón suficiente para explorar el problema.

Answer 2

En $P \ne NP$ es la mejor manera que conocemos de formular la creencia (que se expresó incluso antes de que se planteara formalmente el problema) de que ciertos problemas algorítmicos específicos (como encontrar un ciclo hamiltoniano en un grafo) requieren un número exponencial de pasos en función de su descripción. La formulación se basa en la importante noción de algoritmo no determinista. La conjetura de que P no es igual a NP es la base de una teoría matemática de la complejidad de notable belleza. Es probable que una prueba de la conjetura conduzca a una mejor comprensión de las limitaciones de la computación que vaya más allá de la propia conjetura. (Un contraejemplo (que no se espera) podría conducir a un cambio importante de nuestra realidad y no sólo de nuestra comprensión de la misma. (Supongo que ésta es una de las principales razones para creer en la conjetura.) Su preocupación es que quizá, debido a la naturaleza asintótica de la conjetura, podamos cuestionar su relevancia real. A saber, los problemas que consideramos intratables pueden seguir siéndolo incluso si P=NP debido a las enormes constantes en el polinomio implicado, o quizás incluso si NP no es igual a P puede haber algoritmos eficientes para casos relevantes de problemas intratables. Estas son preocupaciones serias que se plantean a menudo y a veces hay esfuerzos para estudiarlas científicamente.

En general, parece que estas preocupaciones asintóticas son secundarias en comparación con el problema en sí. Además, hay muchos ejemplos de que el comportamiento asintótico y el comportamiento práctico son similares más allá de lo que dicta la teoría (pero también hay algunos ejemplos en la otra dirección). Hay otras preocupaciones relacionadas con la relevancia para la $P \ne NP$ problema. ¿Es relevante el análisis del peor caso para los problemas prácticos? ¿Se aplica la dureza cuando nos interesa la solución aproximada y no la solución exacta? Estas dos cuestiones (al igual que la cuestión asintótica) pueden considerarse de importancia secundaria en comparación con el $NP \ne P$ problema en sí, pero por lo demás muy importante. De hecho, tanto la dureza de la aproximación como el análisis del caso medio son temas de investigación muy centrales.

(Una observación al margen: hay algo antinatural en la forma en que se utilizan los números de Graham en la pregunta. Se trata de un problema de decisión en el que la respuesta es siempre afirmativa cuando n es suficientemente grande. Y existe un algoritmo simple de tiempo polinómico en función de n para decidir la respuesta para a cada n dado. Así que la relevancia de este ejemplo particular (que es interesante) para la pregunta formulada sobre problemas NP completos (que también es interesante) no es tan fuerte).

Por último, en cuanto a la relevancia. Andreas planteó la interesante posibilidad de que NP=P pero las constantes implicadas son tan enormes que el algoritmo polinómico para resolver problemas completos NP no es en absoluto práctico. Una posibilidad interesante relacionada es que incluso exista un algoritmo polinómico práctico para problemas NP completos, pero que encontrar este algoritmo en sí mismo sea computacionalmente intratable. Como ya he dicho, ambas posibilidades se consideran poco plausibles. Incluso si fueran ciertas, no dañarían la relevancia del problema NP=P a la hora de hacer la distinción central entre problemas intratables y tratables. Para que estas preocupaciones interesante hay que idear un marco teórico para estudiarlos, y luego estudiarlos de forma fructífera. (Como mencioné anteriormente, esto se hizo para preocupaciones relacionadas con la aproximación y con el comportamiento del caso medio).

Answer 3

Es claramente relevante si existen factible algoritmos para problemas NP-completos, donde estoy utilizando el término "algoritmo factible" en el sentido informal de un algoritmo que realmente podríamos ejecutar rápidamente en la práctica en problemas de interés práctico. Esta es la cuestión principal.

La relevancia de la $P = NP$ pregunta radica en su pertinencia percibida con respecto a la Pregunta Principal. Evidentemente, para demostrar que $P = NP$ es una cuestión relevante, bastaría con demostrar el lema de que $P$ es precisamente la clase de problemas con algoritmos factibles.

Por supuesto, el lema es obviamente falso, como usted señala y como otros han señalado (por ejemplo, Yuri Gurevich ). Aun así, hay suficiente solapamiento entre $P$ y la clase de problemas con soluciones factibles que resuelven el $P=NP$ sería un paso parcial importante para responder a la Pregunta Principal. En este sentido $P=NP$ es una cuestión relevante.

Answer 4

Para responder a la pregunta de su título, creo que se basa en una premisa falsa. No creo que nadie afirme seriamente que "P vs NP" sea "necesariamente relevante", en el sentido en que pareces entender "relevante"; es decir, no creo que nadie afirme que una solución "P vs NP" tendrá automáticamente un impacto significativo en la forma en que se utiliza la informática. Sin embargo, hay buenas razones para pensar que la cuestión tiene un interés teórico sustancial.

En cuanto a tu pregunta del final, si P=NP entonces, para cualquier problema, el algoritmo que diagonaliza a través de todos los posibles algoritmos de tiempo P está garantizado que es un algoritmo de tiempo P para el problema. (Por supuesto, este algoritmo sería muy lento.) Así que en cierto sentido no puede haber una prueba no efectiva de que P=NP.