Limits on alternation trading proofs for time-space lower bounds
From MaRDI portal
Publication:496301
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
lower boundssatisfiabilityalternationalternating Turing machinesalternating quantifiersquantifier complexityrules of inferencetime-space tradeoffs
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