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.
- ¿Debo aceptar un rol de analista tecnológico de $ 85K con Accenture en SF o estudiar en un campo de entrenamiento de codificación a largo plazo?
- ¿Por qué los megabytes no son exactamente 1 millón de bytes?
- Si el área de interés principal de uno es la teoría de la información, ¿en qué debería especializarse, a nivel de pregrado?
- ¿Cómo podemos usar dos SO en la misma computadora?
- ¿Cómo es tomar CS 124 (Sistemas operativos) en Caltech?
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).