Improving exhaustive search implies superpolynomial lower bounds

DOI10.1145/1806689.1806723zbMath1293.68177WikidataQ57568006 ScholiaQ57568006MaRDI QIDQ2875149

R. Ryan Williams

Publication date: 13 August 2014

Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1806689.1806723

zbMATH Keywords

lower bounds; exact algorithms; time-space tradeoffs; improved exponential algorithms

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Unnamed Item, Unnamed Item, An improved deterministic \#SAT algorithm for small De Morgan formulas, A satisfiability algorithm and average-case hardness for formulas over the full binary basis, On uniformity and circuit lower bounds, Improved simulation of nondeterministic Turing machines, Mining circuit lower bound proofs for meta-algorithms, Robust simulations and significant separations, Strong ETH and resolution via games and the multiplicity of strategies, Circuit lower bounds from learning-theoretic approaches, Sublinear Root Detection and New Hardness Results for Sparse Polynomials over Finite Fields, Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases, Satisfiability Certificates Verifiable in Subexponential Time, NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o(loglogn) Depth