Ce papier de Hunter Monroe investigate la relation entre les théories axiomatiques et leurs systèmes de preuves, se concentrant sur le moment où une théorie peut p-simuler une autre.
Les principaux résultats sont :
1. Si une théorie calculable en nombre (c.e.) S interprète efficacement S+ϕ, alors S p-simule S+ϕ. Cela signifie que l'interprétation cartographie une preuve de S+ϕ en une preuve de S.
2. S prouve "S interprète efficacement S+ϕ" si et seulement si S prouve "S p-simule S+ϕ".
3. Aucune théorie unique S ne peut p-simuler toutes les autres théories. Cela implique P≠NP≠coNP.
4. S ne p-simule pas toutes les théories, car elles seraient indémontrables et non calculables.
5. Le papier propose des conjectures plus fortes que "aucun système de preuve optimal n'existe" qui impliquent l'Hypothèse de Feige, l'existence de fonctions à sens unique et des bornes inférieures des circuits.
Concepts clés et techniques :
- **p-Simulation** : C'est une forme plus forte de simulation entre théories. Cela signifie qu'il existe une fonction calculable en temps polynomial qui cartographie les preuves d'une théorie vers les preuves d'une autre théorie.
- **Interprétation** : C'est une correspondance entre les thèses d'une théorie vers les thèses d'une autre théorie qui respecte les connecteurs logiques.
- **Conjectures** : Le papier propose des conjectures qui impliquent l'existence de fonctions à sens unique et des bornes inférieures des circuits, allant au-delà de l'hypothèse "aucun système de preuve optimal n'existe".
Implications :
- Les résultats montrent que la capacité d'une théorie à p-simuler une autre est étroitement liée à la complexité de la démonstration de certaines affirmations dans les théories.
- Le fait non-rélativisé que aucune théorie calculable en nombre (c.e.) n'interprète toutes les théories calculables en nombre (c.e.) est crucial pour les implications.
- Le papier explore comment ce cadre peut être utilisé pour aborder d'autres questions ouvertes en théorie de la complexité, telles que l'Hypothèse de Feige et les bornes inférieures des circuits.
Dans l'ensemble, le papier fournit une compréhension plus approfondie de la relation entre les théories axiomatiques et leurs systèmes de preuves, et montre comment cela peut être utilisé pour aborder des questions ouvertes importantes en théorie de la complexité.