Inductive time-space lower bounds for SAT and related problems

DOI10.1007/S00037-007-0221-1MaRDI QIDQ2460033zbMATH OpenOpenAlexFDO

Authors Ryan Williams

Publication date 14 November 2007

Published in Computational Complexity (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://doi.org/10.1007/s00037-007-0221-1

zbMATH Keywords

bounded nondeterminismdiagonalizationlower boundspolynomial-time hierarchysatisfiabilityTime-space tradeoffs

Mathematics Subject Classification ID

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

Recommendations

• Time-space lower bounds for satisfiability
• Time-space tradeoffs for SAT on nonuniform machines
• A survey of lower bounds for satisfiability and related problems.
• Time-space tradeoffs for satisfiability
• Time‐Space Lower Bounds for the Polynomial‐Time Hierarchy on Randomized Machines

Cited in

(17)

• Time-space tradeoffs for satisfiability
• Unifying known lower bounds via geometric complexity theory
• Improving exhaustive search implies superpolynomial lower bounds
• Improving exhaustive search implies superpolynomial lower bounds
• Time-space efficient simulations of quantum computations
• Time‐Space Lower Bounds for the Polynomial‐Time Hierarchy on Randomized Machines
• Local reductions
• Time-space lower bounds for satisfiability
• Deterministic versus nondeterministic time and lower bound problems
• Limits on alternation trading proofs for time-space lower bounds
• Pseudorandom bits and lower bounds for randomized Turing machines
• An Improved Time-Space Lower Bound for Tautologies
• Automata, Languages and Programming
• Time-space tradeoffs for SAT on nonuniform machines
• An improved time-space lower bound for tautologies
• Towards stronger depth lower bounds
• Time-space lower bounds for simulating proof systems with quantum and randomized verifiers

This page was built for publication: Inductive time-space lower bounds for SAT and related problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2460033)