A survey of lower bounds for satisfiability and related problems.

DOI10.1561/0400000012MaRDI QIDQ3587579zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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)

Recommendations

• Time-space lower bounds for satisfiability
• scientific article; zbMATH DE number 2156275
• Time-space lower bounds for satisfiability
• Automata, Languages and Programming
• A time lower bound for satisfiability

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
• Amplifying circuit lower bounds against polynomial time, with applications
• scientific article; zbMATH DE number 2156275 (Why is no real title available?)
• 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)