The p-optimality obstruction conjecture for analyzable proof systems

Let QQ 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 QQ, if QQ is analyzable, then QQ 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

Never refreshed

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.