El requisito estándar para cualquier sistema deductivo (es decir, sistema de Axiomas y reglas de inferencia a partir del cual podemos generar pruebas) es que el sistema deductivo debe ser verificable en tiempo polinómico. En otras palabras, si “prueba” algo usando un sistema deductivo dado, entonces verificar que la prueba es básicamente un proceso mecánico paso a paso y no requiere una intuición real. Si lo piensa, este es realmente un requisito bastante importante. Imagine un sistema de prueba que * no * fuera verificable en tiempo polinómico. Luego, en algún paso, podría parecer algo así como “y suponiendo que un milagro resuelva el paso 312, …” correcto. No muy convincente. Para ser convincente, la prueba tiene que ser algo que sea fácil de verificar.
Dado esto, y suponiendo que su sistema de prueba sea lo suficientemente potente, se mantendrán las siguientes propiedades:
- Dada una declaración S y el sistema deductivo A, determinar si hay una prueba de S dentro de A es indecidible.
- Dada una declaración S, un sistema deductivo A y una cadena L de longitud N (ignoramos el contenido de L: solo nos importa su longitud), determinar si hay una deducción de S con una longitud de L o menos es NP -Completar.
- Dada una declaración S, un sistema deductivo A y un polinomio fijo p (*), determinar si hay una deducción de S con una longitud de p (| S |) o menos es NP-Completo.
Ahora, pregunta si la prueba está “contenida en NP”. Bueno, eso depende. Si desea saber si hay una prueba de una declaración dada, en general, entonces el problema claramente no está en NP, ya que el problema ni siquiera es decidible. Pero determinar dentro de un límite de longitud, en términos generales, está en NP.
- ¿Un sistema en un estado estable alguna vez hará un túnel cuántico en otro estado?
- ¿Cuáles son algunas de las nuevas tecnologías que explotan la mecánica cuántica?
- En un futuro relativamente lejano, ¿la computación cuántica hará obsoleta la teoría del caos?
- ¿Cómo se asigna el aprendizaje automático a las operaciones de computación cuántica?
- ¿Existe un límite para la cantidad de qubits que puede tener una computadora cuántica?
Sin embargo, ¿qué pasa con los sistemas de prueba más esotéricos? Quizás un sistema de prueba que permita probar problemas NP-duros en un solo paso. Bueno, lamentablemente, estos sistemas de prueba se verán dolorosamente sin prueba. Porque para cualquier enunciado S de longitud N, si hay una prueba de longitud Q para el enunciado S en A, entonces también hay un enunciado que se ve así: “S es verdadero porque hay una deducción de S en A de longitud Q “. La declaración se puede hacer valer sin ninguna prueba de respaldo. Como dije antes, se verá como “Un milagro sucedió en el paso 312 …”
