A Survey of Lower Bounds for Satisfiability and Related Problems

DOI10.1561/0400000012zbMath1193.68122OpenAlexW2612879297MaRDI QIDQ3587579

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Local Reductions, Local reduction, Amplifying circuit lower bounds against polynomial time, with applications, An Improved Time-Space Lower Bound for Tautologies, On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions, On counting propositional logic and Wagner's hierarchy, Arithmetic circuits: the chasm at depth four gets wider, An improved time-space lower bound for tautologies, Limits on alternation trading proofs for time-space lower bounds, Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle