¿Podría probar que P = NP también es un problema de NP?

Supongamos por un momento que tenemos un sistema formal para derivar pruebas. Llamaremos a este sistema “Theta” por el momento. Puede basarse en la teoría de conjuntos (por ejemplo, ZFC) o en la aritmética de Peano con lógica de segundo orden u otros formalismos. Todo lo que necesitamos de él por el momento es que debe ser “verificable en tiempo polinómico”. Lo que queremos decir con “tiempo polinómico verificable” es que existe un algoritmo de tiempo polinómico para analizar una deducción en Theta y determinar si Theta es legal.

Para demostrar de manera convincente que P = NP o P! = NP, debe poder demostrar que existe un sistema deductivo en el que podría expresar su trabajo

Ahora, supongamos también que es posible expresar la noción de P y NP y la noción de equivalencia (o no equivalencia) entre estas clases.

Dado esto, ahora podemos hacer esta pregunta:

¿Existe una deducción en Theta de longitud L (expresada en base-1 *) con la conclusión de que P! = NP?

De manera similar, podríamos pedir P == NP. La noción de que L se expresa en base 1 significa que L podría verse así:

11111111111111111111111111111111… 1111

El valor de L es el número de ‘1’s. Tenga en cuenta que si permitimos que L se exprese en la base 2 o en la base 10, el problema probablemente requiera al menos un tiempo exponencial a lo largo de la entrada, porque podemos elegir un valor para L como “1000000000000000 … 00”, y comenzar a decir , 100 caracteres, pero luego permiten pruebas de longitud de googol.

La pregunta planteada es en NP. Sin embargo, eso no lo hace fácil. En general, dada una declaración S (expresada en el lenguaje de Theta), podemos formar el lenguaje de los problemas:

¿Hay una deducción en Theta de longitud L (expresada en base-1 *) con la conclusión expresada por S?

Esto, suponiendo que Theta sea lo suficientemente potente en su capacidad expresiva, es un problema NP-completo.

Considere ahora, un problema relacionado donde eliminamos el requisito de longitud:

¿Hay una deducción en Theta con la conclusión expresada por S?

Esto, según el primer teorema de incompletitud de Goedel, es indecidible. El problema que tenemos es que tenemos una instancia particular de ‘S’ donde ‘S’ es la declaración P! = NP (o para una pequeña minoría de investigadores, la expectativa es P = NP).

Suponiendo que realmente exista una prueba, hay un valor válido para L que podemos usar para encontrar la prueba, pero no tenemos forma de establecer límites para L. Además, ¡realmente no sabemos que existe una prueba! (Sin embargo, diría que casi con seguridad existe: el mundo en el que no existe una prueba en ambos sentidos se vuelve bastante extraño).

No es realmente obvio lo que eso significaría. No hay un parámetro libre aquí. Si [math] P = NP [/ math], entonces hay algún algoritmo que enumera todos los pasos de la prueba. Si [math] P \ neq NP [/ math], hay algún algoritmo que enumera todos los pasos de la prueba. (Si [math] P = NP [/ math] es independiente de ZFC, entonces presumiblemente hay algún algoritmo que sigue los pasos de eso.) En cualquier caso, dado que no hay un parámetro libre, el tiempo de ejecución es solo [math] O (1) [/ matemáticas].

Lo que podría pedir sería un algoritmo que, dada una secuencia de deducciones lógicas, determinara si esa secuencia era válida. ¿Podría tal algoritmo ejecutarse en tiempo polinómico? Tal vez, depende de lo que permita como “deducciones lógicas”. Sin embargo, para el software de verificación de pruebas automatizado existente como Coq, la respuesta es ‘no’. (Remito al lector interesado a esta página de MathOverflow: ¿Complejidad algorítmica de la verificación formal de la prueba?)