Regular Resolution Versus Unrestricted Resolution

DOI10.1137/0222044zbMath0781.68099OpenAlexW2086871557MaRDI QIDQ3137703

Andreas Goerdt

Publication date: 10 October 1993

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

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

zbMATH Keywords

lower boundrestrictionresolution

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Mechanization of proofs and logical operations (03B35)

Related Items

Characterizing Tseitin-Formulas with Short Regular Resolution Refutations ⋮ Regular and General Resolution: An Improved Separation ⋮ Limitations of Restricted Branching in Clause Learning ⋮ The NP-hardness of finding a directed acyclic graph for regular resolution ⋮ Limitations of restricted branching in clause learning ⋮ The complexity of resolution refinements ⋮ Relative efficiency of propositional proof systems: Resolution vs. cut-free LK ⋮ Reflections on Proof Complexity and Counting Principles ⋮ Characterizing Tseitin-formulas with short regular resolution refutations

This page was built for publication: Regular Resolution Versus Unrestricted Resolution