Limits on alternation trading proofs for time-space lower bounds
DOI10.1007/S00037-015-0104-9zbMATH Open1338.68080OpenAlexW2152166524WikidataQ113906246 ScholiaQ113906246MaRDI QIDQ496301FDOQ496301
Authors: Samuel R. Buss, 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
Recommendations
lower boundssatisfiabilityalternating Turing machinesalternating quantifiersalternationquantifier 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)
Cites Work
- Lower Bounds for Quantum Communication Complexity
- Natural proofs
- Algebrization
- Time-space lower bounds for satisfiability
- A survey of lower bounds for satisfiability and related problems.
- Time-space tradeoffs for SAT on nonuniform machines
- Title not available (Why is that?)
- Inductive time-space lower bounds for SAT and related problems
- A time lower bound for satisfiability
- Alternation-Trading Proofs, Linear Programming, and Lower Bounds
- Alternation-trading proofs, linear programming, and lower bounds (extended abstract)
- Towards separating nondeterminism from determinism
- Time‐Space Lower Bounds for the Polynomial‐Time Hierarchy on Randomized Machines
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Title not available (Why is that?)
- Time-space tradeoffs for counting NP solutions modulo integers
Cited In (4)
This page was built for publication: Limits on alternation trading proofs for time-space lower bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q496301)
