Frege systems for quantified Boolean logic

Journal article

We define and investigate Frege systems for quantified Boolean formulas (QBF). For these new proof systems, we develop a lower bound technique that directly lifts circuit lower bounds for a circuit class C to the QBF Frege system operating with lines from C. Such a direct transfer from circuit to proof complexity lower bounds has often been postulated for propositional systems but had not been formally established in such generality for any proof systems prior to this work.

This leads to strong lower bounds for restricted versions of QBF Frege, in particular an exponential lower bound for QBF Frege systems operating with AC0[p] circuits. In contrast, any non-trivial lower bound for propositional AC0[p]-Frege constitutes a major open problem.

Improving these lower bounds to unrestricted QBF Frege tightly corresponds to the major problems in circuit complexity and propositional proof complexity. In particular, proving a lower bound for QBF Frege systems operating with arbitrary P/poly circuits is equivalent to either showing a lower bound for P/poly or for propositional extended Frege (which operates with P/poly circuits).

We also compare our new QBF Frege systems to standard sequent calculi for QBF and establish a correspondence to intuitionistic bounded arithmetic.

Authors: Beyersdorff, O; Bonacina, I; Chew, L; Pich, J

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Association for Computing Machinery
• Journal: Journal of the ACM
• Volume: 67
• Issue: 2
• Article number: 9
• Publication date: 2020-04-01
• Acceptance date: 2020-02-01
• DOI: 10.1145/3381881
• EISSN: 1557-735X
• ISSN: 0004-5411
• Language: English
• Keywords: sequent calculus; FFR; QBF proof complexity; strategy extraction; simulations; intuitionistic logic; Frege systems; lower bounds