New separations in propositional proof complexity.

摘要

The problem of recognizing satisfiable formulas and propositional tautologies is ubiquitous in computer science. Propositional proof systems are methods for establishing that a propositional formula is a tautology. In general, proof systems correspond to algorithms for satisfiability so that lower bounds on proof sizes in a given system correspond to lower bounds on the run time of the related satisfiability algorithms. Moreover, the question of proof sizes is intimately connected to questions such as NP versus coNP.; In this dissertation, we study the sizes of proofs in different propositional proof systems. We prove new lower bounds on the sizes of proofs in the Res( k) systems, we prove that constant-depth Frege systems with counting axioms do not polynomially simulate constant-depth Frege systems with counting gates, and we prove that constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations. As corollaries to these results, we obtain the first separation of the Nullstellensatz and polynomial calculus systems with respect to size, and an exponential separation between constant-depth Frege systems and constant-depth Frege systems with counting axioms with respect to constant-width CNFs. The lower bounds for the Res(k) systems include: (1) The 2n to n weak pigeonhole principle requires size $2Wne$ to refute in Res($logn/loglogn$). (2) For each k, there exists a constant w > k so that random w-CNFs in n variables require size $2Wne$ to refute in Res(k). (3) We demonstrate sets of clauses on n variables that have polynomial size Res(k + 1) refutations, but require size $2Wne$ to refute in Res(k).; Our lower bounds for proof sizes are proved using extensions of the switching lemma technique. The lower bound proofs for the Res(k) systems use a method we call switching with small restrictions, and the lower bound proof for constant-depth Frege with counting axioms uses a switching lemma that makes random substitutions rather than 0/1 restrictions. The switching lemma for small restrictions allows us to prove the first separation between depth d circuits of bottom fan-in k + 1 and depth d circuits of bottom fan-in k.