12.4 Proof complexity and computational complexity

Proof complexity and computational complexity are two intertwined fields in theoretical computer science. They explore the resources needed to prove statements and solve problems, shedding light on the fundamental nature of computation and reasoning.

This section dives into propositional proof systems, focusing on resolution and Frege systems. It then examines proof size, ###np-completeness_0###, and the Cook-Reckhow theorem, revealing connections between proof efficiency and computational complexity classes.

Propositional Proof Systems

Resolution and Frege Systems

Top images from around the web for Resolution and Frege Systems

• 

  Weighted Sum-of-Squares Lower Bounds for Univariate Polynomials Imply $$\text{VP} \neq \text{VNP ... View original

  Is this image relevant?

• 

  Computational complexity theory - Wikipedia View original

  Is this image relevant?

• 

  Propositional Logic Proof using I.P. or C.P or rules of inference - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  Weighted Sum-of-Squares Lower Bounds for Univariate Polynomials Imply $$\text{VP} \neq \text{VNP ... View original

  Is this image relevant?

• 

  Computational complexity theory - Wikipedia View original

  Is this image relevant?

1 of 3

Top images from around the web for Resolution and Frege Systems

• 

  Weighted Sum-of-Squares Lower Bounds for Univariate Polynomials Imply $$\text{VP} \neq \text{VNP ... View original

  Is this image relevant?

• 

  Computational complexity theory - Wikipedia View original

  Is this image relevant?

• 

  Propositional Logic Proof using I.P. or C.P or rules of inference - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  Weighted Sum-of-Squares Lower Bounds for Univariate Polynomials Imply $$\text{VP} \neq \text{VNP ... View original

  Is this image relevant?

• 

  Computational complexity theory - Wikipedia View original

  Is this image relevant?

1 of 3

• Propositional proof systems are formal systems for proving propositional tautologies
• Resolution is a simple and widely used propositional proof system based on the resolution inference rule
  • Operates on clauses (disjunctions of literals)
  • Resolves two clauses containing complementary literals to derive a new clause
  • Refutation proofs derive the empty clause, indicating the unsatisfiability of the original formula
• Frege systems are a class of propositional proof systems based on a fixed set of axioms and inference rules
  • Closely resemble natural deduction systems used in mathematical logic
  • Proofs are sequences of formulas, each derived from previous formulas using the inference rules
• Extended Frege systems augment Frege systems with the ability to introduce new variables and definitions
  • Allows for more concise proofs by defining intermediate formulas
  • Can lead to exponentially shorter proofs compared to standard Frege systems for some formulas

Polynomial Simulation

• Polynomial simulation is a relationship between two propositional proof systems
• A proof system $[P](https://www.fiveableKeyTerm:p)$ polynomially simulates another proof system $Q$ if there exists a polynomial-time computable function that translates $Q$-proofs into $P$-proofs
  • The size of the resulting $P$-proof is polynomially bounded by the size of the original $Q$-proof
• Polynomial simulation captures the relative efficiency of proof systems
  • If $P$ polynomially simulates $Q$, then $P$ is at least as efficient as $Q$ in terms of proof size
• Frege systems and extended Frege systems are known to polynomially simulate resolution
  • This implies that Frege and extended Frege systems are at least as powerful as resolution in terms of the sizes of proofs they can generate

Proof Complexity

Proof Size and NP-Completeness

• Proof complexity studies the sizes of proofs in various propositional proof systems
• The size of a proof is the number of symbols or lines required to write down the proof
  • Measured as a function of the size of the formula being proven
• The goal is to understand the efficiency of proof systems and the inherent difficulty of proving certain propositional formulas
• Many propositional tautologies arising from NP-complete problems have been shown to require super-polynomial proof size in various proof systems
  • Examples include tautologies based on the pigeonhole principle and graph coloring problems
• NP-completeness plays a crucial role in proof complexity
  • If NP $\neq$ co-NP, then there exist propositional tautologies with no polynomial-size proofs in any propositional proof system
  • This is a consequence of the Cook-Levin theorem, which establishes the NP-completeness of the propositional satisfiability problem (SAT)

Cook-Reckhow Theorem and Lower Bounds

• The Cook-Reckhow theorem characterizes the efficiency of propositional proof systems in terms of the NP-completeness of the tautology recognition problem
  • A propositional proof system is considered efficient if the tautology recognition problem for that system is in NP
  • In other words, if there exists a polynomial-time algorithm to verify the correctness of proofs in that system
• The theorem implies that NP $\neq$ co-NP is equivalent to the existence of a propositional proof system in which the tautology recognition problem is not in NP
• Super-polynomial lower bounds on proof size have been established for various propositional proof systems
  • Examples include exponential lower bounds for resolution proofs of pigeonhole principle tautologies and Tseitin tautologies on expander graphs
• These lower bounds demonstrate the limitations of specific proof systems and provide insights into the difficulty of proving certain classes of tautologies
• Proving lower bounds on proof size is a central challenge in proof complexity and has connections to fundamental questions in computational complexity theory, such as the P vs. NP problem