A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution

DOI10.1137/S0097539703428555zbMath1059.03063OpenAlexW2137423523WikidataQ124811179 ScholiaQ124811179MaRDI QIDQ4651510

Russell Impagliazzo, Nathan Segerlind, Samuel R. Buss

Publication date: 21 February 2005

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539703428555

zbMATH Keywords

lower boundsresolutionBoolean circuit complexityrandom restrictionpropositional proof complexityrandom CNFs\(k\)-DNFsswitching lemmascircuit bottom fan-inSipser functionsweak pigeonhole principles

Mathematics Subject Classification ID

Mechanization of proofs and logical operations (03B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Related Items (23)

On the Proof Complexity of Paris-Harrington and Off-Diagonal Ramsey Tautologies ⋮ On the automatizability of resolution and related propositional proof systems ⋮ Exponential separation between Res(\(k\)) and Res(\(k+1\)) for \(k \leqslant \varepsilon\log n\) ⋮ Parameterized Parallel Computing and First-Order Logic ⋮ A note about \(k\)-DNF resolution ⋮ FRAGMENTS OF APPROXIMATE COUNTING ⋮ Relativization makes contradictions harder for resolution ⋮ The limits of tractability in resolution-based propositional proof systems ⋮ Lower bounds for \(k\)-DNF resolution on random 3-CNFs ⋮ On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution ⋮ Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution ⋮ Partially definable forcing and bounded arithmetic ⋮ The treewidth of proofs ⋮ Unnamed Item ⋮ The Complexity of Propositional Proofs ⋮ Parameterized Complexity of DPLL Search Procedures ⋮ Short propositional refutations for dense random 3CNF formulas ⋮ An Exponential Lower Bound for Width-Restricted Clause Learning ⋮ Short Proofs Are Hard to Find ⋮ Resolution and the binary encoding of combinatorial principles ⋮ Separation results for the size of constant-depth propositional proofs ⋮ LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE ⋮ On Linear Resolution

This page was built for publication: A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution