Limits on alternation trading proofs for time-space lower bounds

DOI10.1007/s00037-015-0104-9zbMath1338.68080OpenAlexW2152166524WikidataQ113906246 ScholiaQ113906246MaRDI QIDQ496301

Samuel R. Buss, R. Ryan Williams

Publication date: 21 September 2015

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-015-0104-9

zbMATH Keywords

lower boundssatisfiabilityalternationalternating Turing machinesalternating quantifiersquantifier complexityrules of inferencetime-space tradeoffs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle, Unifying known lower bounds via geometric complexity theory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Time-space tradeoffs for counting NP solutions modulo integers
• Inductive time-space lower bounds for SAT and related problems
• A time lower bound for satisfiability
• Algebrization
• Alternation-Trading Proofs, Linear Programming, and Lower Bounds
• Towards separating nondeterminism from determinism
• Time‐Space Lower Bounds for the Polynomial‐Time Hierarchy on Randomized Machines
• Time-space lower bounds for satisfiability
• A Survey of Lower Bounds for Satisfiability and Related Problems
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Lower Bounds for Quantum Communication Complexity
• Natural proofs
• Time-space tradeoffs for SAT on nonuniform machines