¿Es P=NP relevante para encontrar pruebas de proposiciones matemáticas cotidianas?

Question

Descargo de responsabilidad: no sé mucho sobre la teoría de la complejidad más allá de, por ejemplo, una buena clase de licenciatura.

Cada vez con más frecuencia me encuentro con afirmaciones de teóricos de la complejidad de que, en el improbable caso de que se demostrara P=NP y se encontrara un algoritmo con constantes razonables, los matemáticos ya no se molestarían en demostrar las cosas porque podríamos simplemente utilizar nuestro algoritmo de tiempo P para buscar pruebas. Normalmente esto es parte de un argumento de por qué todos los matemáticos y lógicos deberían preocuparse mucho por P=?=NP.

Creo que la mayoría de estas afirmaciones son exageraciones del primer párrafo completo de la página 8 del Cook's descripción del problema para el Instituto de la Arcilla (que a su vez se afirma de forma totalmente razonable y sin exagerar).

Sin embargo, de la descripción del Instituto Clay se desprende claramente que P=NP sólo es relevante para clases de problemas, parametrizados por algún número entero $n$ para lo cual ya hemos demostrado las tres cosas siguientes:

1. la cuestión no es independiente de los axiomas que hayamos elegido ( $T\vdash \phi\vee T\vdash \neg\phi$ )
2. cualquier prueba de la proposición debe tener un tamaño como máximo polinomial en $n$
3. cualquier prueba de la negación de la proposición debe tener un tamaño como máximo polinomial en $n$

De esta manera sabemos que existe una prueba de la proposición o de su negación, y el problema de búsqueda de la que existe cae dentro de NP, por lo que podemos encajar las dos búsquedas y detenernos cuando una de ellas tenga éxito.

Esto me desconcierta. La mayoría de las proposiciones que interesan a los matemáticos no vienen en clases con parámetros enteros, y mucho menos en clases con límites de tamaño de prueba conocidos. Normalmente vienen en clases de tamaño 1 sin conocimiento del tamaño de la prueba. ¿Existe algún truco para convertir los tipos de resultados que interesan a los matemáticos en estas clases con parámetros enteros y límites polinómicos?

Ejemplo: ¿cómo se haría esto para la cuestión de si la CH es o no independiente de la ZFC?

Artículo de JSL de Cook y Reckhow La eficacia relativa de los sistemas de prueba proposicional (que parece ser el punto de partida de la literatura) en realidad menciona que si se toma la clase de problema para que consista en todas las proposiciones en algún sistema de prueba (como el cálculo de predicados de primer orden), se toma la longitud de la proposición como el parámetro, y se toma la pregunta para que sea "¿está implicado por los axiomas?", entonces en el momento en que se publicó el documento (1979) no se conocía ningún sistema de prueba del mundo real que tuviera la propiedad deseada, y se conocían unos pocos no para tener la propiedad deseada.

Supongo que estoy siendo un poco perezoso aquí, ya que el estudio de qué problemas tienen esta propiedad es todo un subcampo con mucha literatura que podría leer, pero realmente sólo estoy interesado en saber si los resultados positivos de ese subcampo justifican o no las afirmaciones que he estado escuchando últimamente. Una referencia a un artículo que contenga el "truco" anterior estaría bien como respuesta.

Answer 1

Permítanme abordar la cuestión al principio de la pregunta original: Si se demostrara P=NP y se encontrara un algoritmo con constantes razonables, ¿dejarían los matemáticos de intentar demostrar cosas? El conjunto NP relevante en esta situación parece ser el $L_1$ de la respuesta de Ryan Williams, que considero (o decodifico) como el conjunto de pares formado por una proposición $P$ que hay que demostrar y un límite superior $n$ , escrito en notación unaria, para la longitud de la prueba. Si tuviéramos un algoritmo de tiempo polinómico para este conjunto NP, entonces podría aplicarlo como sigue. Tomar $P$ ser alguna propuesta en la que estoy tentado a trabajar, y tomar $n$ para ser más grande que cualquier prueba que tenga tiempo de escribir en mi vida. Si el algoritmo, aplicado a estas entradas, dice "no", entonces no debería trabajar en este problema, porque cualquier prueba sería demasiado larga para mí. Si el algoritmo dice que "sí", entonces todavía no debería trabajar en el problema porque un algoritmo de tiempo P para el problema de Ryan $L_2$ podría encontrar la prueba para mí. Todo esto, sin embargo, depende de una comprensión extremadamente optimista de las "constantes razonables". El $n$ que he elegido es (espero) bastante grande, por lo que incluso un algoritmo de tiempo cuadrático (con un coeficiente pequeño en el término cuadrático) podría llevar mucho tiempo (más que mi vida).

La conclusión es que, si se demostrara P=NP con constantes plausibles en el tiempo de ejecución, no sería una tontería que siguiera intentando demostrar teoremas. (Incluso si fuera una tontería, seguiría intentándolo de todos modos, en parte porque es divertido y en parte porque a la gente podría gustarle más mi demostración que la primera lexicográficamente).

Por cierto, el sistema en el que se hacen las pruebas no debería ser, para estos fines, simplemente un sistema axiomático como ZFC con sus axiomas tradicionales y su lógica subyacente. Debería ser un sistema que permita introducir formalmente definiciones. De hecho, debería aproximarse mucho a lo que los matemáticos escriben realmente. La razón es que, aunque sólo busco pruebas lo suficientemente cortas como para escribirlas en mi vida, eso no significa pruebas lo suficientemente cortas como para escribirlas en la notación ZFC primitiva en mi vida. Creo que algunas (si no todas) de las pruebas que he publicado serían, si se escribieran en notación ZFC primitiva, demasiado largas para toda una vida.

Answer 2

Yo mismo pienso que demostrar que P=NP no es necesario ni suficiente para conseguir que los ordenadores resuelvan problemas matemáticos.

No es suficiente: podría producir certificados de verdad largos y prácticamente sin sentido en lugar de pruebas adecuadas que podamos comprender e interesarnos realmente.

No es necesario: como matemáticos no resolvemos el problema totalmente general: "¿Existe una demostración de este enunciado que requiera menos de n símbolos?". Más bien, nos centramos en una subclase muy pequeña que consiste en problemas interesantes y significativos y buscamos pruebas interesantes y significativas. Yo mismo creo que este problema se puede resolver en tiempo polinómico (a grandes rasgos, porque no creo que los humanos tengan habilidades especiales de las que los ordenadores carecerán siempre).

Answer 3

Permítanme intentar una respuesta algo más detallada que las anteriores. No sé si aclara tus dudas, porque no estoy completamente seguro de cuáles son tus preocupaciones. Para cualquier sistema de pruebas, considere los lenguajes

$L_1 = \{ P1^n ~|~n \in {\mathbb N}$ y la proposición $P$ tiene una prueba en el sistema con un máximo de $n$ símbolos $\}$ .

$L_2 = \{ P1^k ~|~n \in {\mathbb N}$ y la proposición $P$ tiene una prueba en el sistema y el $k$ -ésimo bit de la primera prueba lexicográfica de $P$ es 1 $\}$ .

Si $P=NP$ entonces los dos lenguajes anteriores pueden resolverse en tiempo polinómico (para los sistemas de prueba "cotidianos"). Esto permite producir una prueba de cualquier proposición fija $P$ cuando existe, en un tiempo que es polinómico en la longitud de la prueba más corta. No necesitamos conocer de antemano la longitud de la prueba más corta. Por ejemplo, si el SAT se puede resolver en tiempo lineal (un problema abierto), entonces el procedimiento siguiente debería poder implementarse en un tiempo no superior al cuadrático o cúbico de la longitud de la prueba más corta.

Voy a explicar por qué esto es cierto. Supongamos, para ser explícitos, que el tiempo de ejecución para decidir tanto $L_1$ y $L_2$ es como máximo $c \cdot n$ où $n$ es la longitud de entrada. Primero, ejecute el programa para $L_1$ en $P1$ , $(\neg P)1$ , $P1^2$ , $(\neg P)1^2$ , $P1^4$ , $(\neg P)1^4$ , $P1^8$ , $(\neg P)1^8$ etc., hasta que el programa dé como resultado un "sí". El tiempo de ejecución de este procedimiento es de aproximadamente $c(d+2)2^k$ où $d$ es la longitud de la proposición y $2^k$ es la menor potencia de dos que supera la longitud de la prueba más corta. Esto determina un límite superior en la longitud de la prueba más corta hasta un factor multiplicativo de dos. (Realizando una "búsqueda binaria" de forma similar en el intervalo $[2^{k-1},2^k]$ con un lenguaje ligeramente modificado, se podría descubrir la longitud mínima de una prueba si se quiere, llámese $p$ . A nosotros nos basta con tener un buen límite superior de la longitud).

Supongamos que el programa da como resultado "sí" en $P$ (en lugar de $\neg P$ ). A continuación, ejecute el programa para $L_2$ en $P1^1$ , $P1^2$ , $\ldots$ , $P1^p$ (o hasta $P1^{2^k}$ ). Cada llamada devuelve un bit de la primera prueba lexicográfica de $P$ que tiene una longitud $p$ . El tiempo total de ejecución es aproximadamente cuadrático en $p$ (con algunas constantes adicionales $c$ y $d$ ).

Si lo que quieres decir es que incluso este tipo de tiempo de ejecución debe ser poco práctico para las "proposiciones matemáticas cotidianas", tengo que discrepar. Si la constante $c$ en los algoritmos fueran probadamente gigantescos (o más generalmente, los grados de los polinomios en el tiempo de ejecución) entonces esto sería cierto, pero tenemos muy poco conocimiento de los límites de $c$ en este momento.

Answer 4

Resulta que le pedí a una pregunta análoga en Teoría CS StackExchange . Un breve resumen informal es el siguiente. Primero, es indecidible determinar si un teorema dado es demostrable en ZFC, y esto no cambiaría si supiéramos que P=NP. En segundo lugar, para otros teoremas matemáticos (he utilizado la conjetura de Goldbach) si P=NP, y si el teorema tiene una "prueba corta", entonces no sólo podríamos determinar si el teorema es verdadero o falso, también podríamos encontrar una prueba rápidamente. Más concretamente, se podría encontrar una prueba "en un tiempo polinómico de la longitud del enunciado y la longitud de la prueba más corta" (para citar a uno de los encuestados) utilizando La búsqueda universal de Levin algoritmo .

Answer 5

El papel "Una visión personal de la complejidad del caso medio" de Russell Impagliazzo considera cinco mundos diferentes en función de la complejidad media de los casos de problemas NP-completos, uno de ellos ("Algorithmica") con P=NP.

Los diferentes mundos se explican utilizando la famosa anécdota de Gauss y su profesor pidiendo a la clase que sume los números del 1 al 100, por lo que es una lectura agradable para cualquier matemático. El artículo se centra en las consecuencias de las cinco posibilidades diferentes en que el profesor pueda plantear problemas de los que conoce la solución pero que Gauss no puede resolver. Así que no responde a tu pregunta sobre "un truco para convertir las matemáticas en problemas NP", pero te da una idea sobre la pregunta de tu título.