An Improved Time-Space Lower Bound for Tautologies

DOI10.1007/978-3-642-02882-3_43zbMath1248.03078OpenAlexW1485439933MaRDI QIDQ5323091

Scott Diehl, Dieter van Melkebeek, R. Ryan Williams

Publication date: 23 July 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02882-3_43

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

Cites Work

• Time-space tradeoffs for counting NP solutions modulo integers
• Time-space tradeoffs for satisfiability
• Relationships between nondeterministic and deterministic tape complexities
• Time-space lower bounds for satisfiability
• A Survey of Lower Bounds for Satisfiability and Related Problems

This page was built for publication: An Improved Time-Space Lower Bound for Tautologies