The p-optimality obstruction conjecture for analyzable proof systems
The p-optimality obstruction conjecture for analyzable proof systems
Let be a propositional proof system. A proof system is analyzable when its associated proof-analysis problem admits the efficient analysis described in the paper, and it is p-optimal when it simulates every propositional proof system with polynomial overhead.
Analyzability requires lower bounds or proofs that are hard to find. For every propositional proof system , if is analyzable, then is not p-optimal.
This is a weaker proposed conclusion than non-optimality: failure of p-optimality permits explicit tautology families whose proofs are either long or short but computationally hard to find. The conjecture remains open in the source.
Sources & referencesView supporting material
Primary source
Noel Arteche, Albert Atserias, Susanna F. de Rezende and Erfan Khaniki, “The Proof Analysis Problem”, arXiv:2506.16956 (2026).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.