Polynomial Calculus for Quantified Boolean Logic: Lower Bounds through Circuits and Degree

Olaf Beyersdorff, Kaspar Kasche, Luc Nicolas Spachmann

TL;DR

This paper introduces a novel characterization of proof sizes in Polynomial Calculus for Quantified Boolean Logic (Q-PC) using a circuit model called Polynomial Decision Lists (PDLs). This connection allows for the derivation of new size-degree relationships and the establishment of incomparable proof systems for Q-PC over different fields, pushing the boundaries of our understanding of proof complexity for quantified logic.

What Problem Does This Paper Address?

Proof complexity aims to understand the minimal size of proofs for logical statements. While significant progress has been made for propositional logic, the study of proof complexity for Quantified Boolean Formulas (QBFs) has lagged, particularly for algebraic proof systems like Polynomial Calculus (PC). Existing lower bounds for QBF proof systems often rely on general semantic techniques that cannot distinguish between different systems. This paper addresses this gap by developing a new theoretical framework to analyze Q-PC, aiming to establish tight connections between proof size and circuit complexity, and to derive stronger, system-specific lower bounds.

Methods

The core of this paper is the establishment of a tight correspondence between the proof size of Q-PC and the size of Polynomial Decision Lists (PDLs). PDLs are a circuit model that generalizes decision lists, using polynomial equations as conditions. The authors first show that Q-PC proof size is polynomially equivalent to PDL size for QBFs with bounded quantifier alternation depth. This connection is then leveraged to derive a size-degree relationship for Q-PC, analogous to existing results for propositional PC but adapted for QBFs. This size-degree relation, along with the PDL characterization, enables the authors to prove new lower bounds on the degree of PDLs for specific functions like parity and modulo k, which in turn translate to lower bounds on Q-PC proof sizes. Finally, the paper shows how to transform PDLs over finite fields into AC⁰[p] circuits, allowing for the transfer of circuit lower bounds to Q-PC and leading to results about the incomparability of Q-PC systems over different fields.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Q-PC meets Circuits: The paper establishes a fundamental equivalence between the proof size of Q-PC and the size of Polynomial Decision Lists (PDLs). This is a significant step in bridging algebraic proof complexity for QBFs with circuit complexity.
  • Size-Degree for QBFs: A novel size-degree relationship is derived for Q-PC, extending previous work on propositional logic and incorporating the quantifier depth of the QBF. This provides a new tool for analyzing proof complexity.
  • New Lower Bound Techniques: The PDL characterization and size-degree relation unlock new methods for proving lower bounds on Q-PC proof sizes, particularly for functions that are hard even for propositional logic.
  • Incomparable Q-PC Systems: By connecting PDLs to AC⁰[p] circuits, the paper demonstrates that Q-PC systems over different fields (finite fields of different characteristics or subfields of complex numbers) are fundamentally incomparable in their proof-finding power.

Key Results

  • A tight characterization of Q-PC proof size by PDL size for QBFs with bounded quantifier alternation depth.
  • A size-degree relation for Q-PC that relates proof size to the minimal degree of polynomials in the refutation, parameterized by quantifier depth.
  • New lower bounds for Q-PC, showing that parity and modulo k functions require exponential size proofs.
  • Demonstration of the incomparability of Q-PC systems over different fields, achieved by transforming PDLs into AC⁰[p] circuits and leveraging known circuit lower bounds.

Limitations and Future Work

The paper focuses on QBFs with bounded quantifier alternation depth for its main characterization. While the results are significant, extending them to QBFs with arbitrary quantifier alternation depth remains an open question. The authors also suggest exploring the wider implications of their P-UDL characterization for other proof systems like Cutting Planes and Frege systems, and investigating whether similar characterizations can be obtained for daglike systems on formulas with unbounded alternation depth.

Summary updated

BibTeX
@article{beyersdorff2024polynomial,
  author = {Olaf Beyersdorff and Kaspar Kasche and Luc Nicolas Spachmann},
  title = {{Polynomial Calculus for Quantified Boolean Logic: Lower Bounds through Circuits and Degree}},
  journal = {Electron. Colloquium Comput. Complex.},
  year = {2024},
  url = {https://openreview.net/forum?id=UUeYxahQn5},
}
Figure