Exponential separation between Res(\(k\)) and Res(\(k+1\)) for \(k \leqslant \varepsilon\log n\)

DOI10.1016/J.IPL.2004.09.024zbMath1173.68714OpenAlexW1494548287MaRDI QIDQ835026

Nathan Segerlind

Publication date: 27 August 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2004.09.024

zbMATH Keywords

computational complexitylower boundsresolutiontheory of computationrandom restrictionspropositional proof complexity\(k\)-DNFsRes(\(k\))switching lemmas

Mathematics Subject Classification ID

Related Items (3)

On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution ⋮ The treewidth of proofs ⋮ The Complexity of Propositional Proofs

Cites Work

• Unrestricted resolution versus N-resolution
• On the automatizability of resolution and related propositional proof systems
• A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution

This page was built for publication: Exponential separation between Res(\(k\)) and Res(\(k+1\)) for \(k \leqslant \varepsilon\log n\)