Limits on alternation trading proofs for time-space lower bounds

DOI10.1007/S00037-015-0104-9MaRDI QIDQ496301zbMATH OpenOpenAlexWikidataFDO

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

zbMATH Keywords

lower boundssatisfiabilityalternating Turing machinesalternating quantifiersalternationquantifier 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)

Recommendations

• Alternation Trading Proofs and Their Limitations
• Time-space tradeoffs for satisfiability
• Time-space tradeoffs for SAT on nonuniform machines
• Alternation-trading proofs, linear programming, and lower bounds
• Time-space lower bounds for satisfiability

Cites work

• scientific article; zbMATH DE number 2156275 (Why is no real title available?)
• scientific article; zbMATH DE number 3353257 (Why is no real title available?)
• A survey of lower bounds for satisfiability and related problems.
• A time lower bound for satisfiability
• Algebrization: a new barrier in complexity theory
• Alternation-trading proofs, linear programming, and lower bounds
• Alternation-trading proofs, linear programming, and lower bounds (extended abstract)
• Inductive time-space lower bounds for SAT and related problems
• Lower Bounds for Quantum Communication Complexity
• Natural proofs
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Time-space lower bounds for satisfiability
• Time-space tradeoffs for SAT on nonuniform machines
• Time-space tradeoffs for counting NP solutions modulo integers
• Time‐Space Lower Bounds for the Polynomial‐Time Hierarchy on Randomized Machines
• Towards separating nondeterminism from determinism

Cited in

(5)

• Time-space tradeoffs for counting NP solutions modulo integers
• Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle
• Alternation Trading Proofs and Their Limitations
• Unifying known lower bounds via geometric complexity theory
• Alternation-trading proofs, linear programming, and lower bounds

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)