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.
References
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
No solutions have been posted yet.