A lower bound for tree resolution

DOI10.1016/0166-218X(94)90132-5zbMath0812.68102OpenAlexW2085389157MaRDI QIDQ1336637

David J. McClurkin

Publication date: 3 November 1994

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(94)90132-5

zbMATH Keywords

bipartite graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Unnamed Item
• Unnamed Item
• Average time analyses of simplified Davis-Putnam procedures
• The intractability of resolution
• Solving satisfiability in less than \(2^ n\) steps
• Eigenvalues and expanders
• Asymptotically optimal switching circuits
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• On the complexity of regular resolution and the Davis-Putnam procedure
• On Concentrators, Superconcentrators, Generalizers, and Nonblocking Networks
• Many hard examples for resolution
• Polynomial size proofs of the propositional pigeonhole principle
• Hard examples for resolution
• The relative efficiency of propositional proof systems

This page was built for publication: A lower bound for tree resolution