TL;DR
This paper establishes a "supercritical tradeoff" for resolution over parities (Res(⊕)), a powerful proof system for demonstrating unsatisfiability. They show that for certain problems, any refutation must be either exponentially large or have a depth that significantly exceeds what's typically expected, even for proofs that are already known to be large. This is a significant step towards understanding the complexity of reasoning with parity, a fundamental operation in computation.
What Problem Does This Paper Address?
The field of propositional proof complexity aims to understand the inherent difficulty of proving that a logical statement is false (unsatisfiable). A key goal is to find lower bounds on the size of proofs required by different proof systems. Resolution is a fundamental proof system, and its extension, Resolution over Parities (Res(⊕)), incorporates linear algebra over F₂ and is crucial for reasoning about parity computations. While exponential lower bounds are known for some proof systems, they remain elusive for stronger systems like Res(⊕).
Previous work has shown that for certain formulas, Res(⊕) refutations must have either exponential size or superlinear depth. However, it was unclear if this was a genuine tradeoff or a limitation of the proof techniques. This paper addresses the question: "Does there exist a formula that admits a short Res(⊕) refutation, yet any such refutation must have either superlinear depth or exponential size?" Answering this affirmatively would demonstrate a "supercritical tradeoff," meaning that for proofs of small size, the required depth is unexpectedly large. This would also shed light on why proving lower bounds for Res(⊕) is so challenging.
Methods
The authors build upon the framework of Alekseev and Itsykson, employing a "lifting argument" that leverages "stifling gadgets." A stifling gadget is a Boolean function that, when used to "lift" a formula, preserves certain hardness properties. Specifically, they use a 2-stifling gadget.
The core of their approach involves:
- A generalized size-depth tradeoff for resolution: They first establish a more flexible tradeoff for resolution itself, which is then lifted to Res(⊕). This involves a sophisticated game-theoretic approach (Prover-Adversary and Prover-Delayer games) and a random walk technique on the refutation graph.
- Lifting to Res(⊕): They adapt the lifting technique to the Res(⊕) system by incorporating parity gates. This allows them to translate tradeoffs in resolution into tradeoffs in Res(⊕).
- Focusing on "supercriticality": The key innovation is to construct formulas that not only exhibit a tradeoff but do so in a way that is "supercritical." This means that for proofs with size below a certain threshold, the depth must be significantly larger than what would be expected even in the worst case.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Supercritical Tradeoff: The paper demonstrates that for Res(⊕), there's a fundamental limit on how "balanced" a proof can be in terms of size and depth. You can't have both arbitrarily small size and arbitrarily small depth simultaneously.
- Lifting Argument Power: The paper showcases the power of lifting arguments, particularly when combined with parity gadgets, to transfer complexity results from simpler proof systems (like resolution) to more powerful ones (like Res(⊕)).
- Game-Theoretic Foundations: The use of Prover-Adversary and Prover-Delayer games provides a robust framework for analyzing proof complexity, allowing for precise control over the properties of refutations.
- Understanding Parity Reasoning: By establishing these tradeoffs in Res(⊕), the work contributes to a deeper understanding of the computational power and limitations of reasoning with parity, which is fundamental in many areas of computer science.
Key Results
The paper presents several key theorems:
- Theorem 1: Establishes a general supercritical tradeoff for Res(⊕) by lifting a known resolution tradeoff. This theorem shows that for a formula constructed using a stifling gadget, any Res(⊕) refutation must have either exponential size or superlinear depth.
- Theorem 2: Provides a concrete example of a formula that exhibits this supercritical tradeoff. This formula has a polynomial-sized resolution refutation but requires either exponential size or superlinear depth for its Res(⊕) refutation. This is the first such result for a proof system lacking known superpolynomial lower bounds on proof size.
- Theorem 4 & 5: These theorems explore specific instances of size-depth tradeoffs for Res(⊕) by applying the lifting technique to formulas with known resolution width properties. They demonstrate how different choices of parameters lead to varying degrees of tradeoff.
Limitations and Future Work
The authors identify two main avenues for future work:
- Constructing a Polynomial-Sized Formula with a Supercritical Tradeoff: The current work establishes a tradeoff, but the formulas constructed might not be polynomial-sized themselves. A key open question is to find a polynomial-sized CNF formula that has a polynomial-sized resolution refutation but requires either superlinear depth or exponential size for its Res(⊕) refutation. This would require strengthening the width-depth tradeoff in resolution.
- Truly Supercritical Tradeoff: The paper aims for a tradeoff where depth is superlinear with respect to the size of the formula. Achieving this would be a significant advancement in understanding the inherent difficulty of proof search.
Summary updated