Este artículo de Hunter Monroe investiga la relación entre las teorías axiomáticas y sus sistemas de prueba, centrándose en cuándo una teoría puede p-simular a otra.
Los resultados principales son:
1. Si una teoría computable enumerable (c.e.) S interpreta eficientemente S+ϕ, entonces S p-simula S+ϕ. Esto significa que la interpretación mapea una prueba de S+ϕ a una prueba de S.
2. S prueba "S interpreta eficientemente S+ϕ" si y solo si S prueba "S p-simula S+ϕ".
3. Ninguna teoría S puede p-simular todas las otras teorías. Esto implica P≠NP≠coNP.
4. S no p-simula todas las teorías, ya que estas serían no probables y no computables.
5. El artículo propone conjeturas más fuertes que "no existe un sistema de prueba óptimo" que impliquen la Hipótesis de Feige, la existencia de funciones de un solo camino y límites inferiores de circuitos.
Conceptos clave y técnicas:
- **p-Simulación**: Esta es una forma más fuerte de simulación entre teorías. Significa que existe una función computable en tiempo polinomial que mapea las pruebas de una teoría a las pruebas de otra teoría.
- **Interpretación**: Esta es una mapeo entre teoremas de una teoría a teoremas de otra teoría que respeta los conectores lógicos.
- **Conjeturas**: El artículo propone conjeturas que implican la existencia de funciones de un solo camino y límites inferiores de circuitos, superando la asunción de "no existe un sistema de prueba óptimo".
Implicaciones:
- Los resultados muestran que la capacidad de una teoría de p-simular a otra está estrechamente relacionada con la complejidad de probar ciertas afirmaciones en las teorías.
- El hecho no relativo de que ninguna teoría c.e. interprete todas las teorías c.e. es crucial para las implicaciones.
- El artículo explora cómo este marco puede ser utilizado para abordar otras preguntas abiertas en la teoría de la complejidad, como la Hipótesis de Feige y los límites inferiores de circuitos.
En resumen, el artículo proporciona una comprensión más profunda de la relación entre las teorías axiomáticas y sus sistemas de prueba y muestra cómo esto puede utilizarse para abordar preguntas abiertas importantes en la teoría de la complejidad.