A lower bound for tree resolution
From MaRDI portal
Recommendations
- A lower bound for treewidth and its consequences
- A complexity gap for tree resolution
- Lower bounds on the size of general branch-and-bound trees
- Improved Lower Bounds for Tree-Like Resolution over Linear Inequalities
- Lower bounds on treespan
- A lower bound on the degree distance in a tree
- An improved lower bound for the elementary theories of trees
- Lower bound on the domination number of a tree
- A lower bound for the irredundance number of trees
- Treewidth computations. II. Lower bounds
Cites work
- scientific article; zbMATH DE number 3566230 (Why is no real title available?)
- scientific article; zbMATH DE number 3325539 (Why is no real title available?)
- Asymptotically optimal switching circuits
- Average time analyses of simplified Davis-Putnam procedures
- Eigenvalues and expanders
- Hard examples for resolution
- Many hard examples for resolution
- On Concentrators, Superconcentrators, Generalizers, and Nonblocking Networks
- On the complexity of regular resolution and the Davis-Putnam procedure
- Polynomial size proofs of the propositional pigeonhole principle
- Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
- Solving satisfiability in less than \(2^ n\) steps
- The intractability of resolution
- The relative efficiency of propositional proof systems
Cited in
(5)- Near optimal seperation of tree-like and general resolution
- scientific article; zbMATH DE number 7238987 (Why is no real title available?)
- A general lower bound for collaborative tree exploration
- scientific article; zbMATH DE number 1522926 (Why is no real title available?)
- Lifting lower bounds for tree-like proofs
This page was built for publication: A lower bound for tree resolution
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1336637)
