A survey of lower bounds for satisfiability and related problems.
DOI10.1561/0400000012zbMATH Open1193.68122OpenAlexW2612879297MaRDI QIDQ3587579FDOQ3587579
Authors: Dieter Van Melkebeek 
Publication date: 8 September 2010
Published in: Foundations and Trends® in Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1561/0400000012
Recommendations
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cited In (18)
- Time-space lower bounds for satisfiability
- Alternation-trading proofs, linear programming, and lower bounds (extended abstract)
- Automata, Languages and Programming
- Inductive time-space lower bounds for SAT and related problems
- A time lower bound for satisfiability
- Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle
- Arithmetic circuits: the chasm at depth four gets wider
- Local reduction
- Results related to threshold phenomena research in satisfiability: Lower bounds
- On counting propositional logic and Wagner's hierarchy
- An Improved Time-Space Lower Bound for Tautologies
- Title not available (Why is that?)
- Amplifying circuit lower bounds against polynomial time, with applications
- Limits on alternation trading proofs for time-space lower bounds
- An improved time-space lower bound for tautologies
- On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions
- Ironic complicity: satisfiability algorithms and circuit lower bounds
- Local reductions
This page was built for publication: A survey of lower bounds for satisfiability and related problems.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3587579)
