An Improved Time-Space Lower Bound for Tautologies

DOI10.1007/978-3-642-02882-3_43MaRDI QIDQ5323091zbMATH OpenOpenAlexFDO

Authors Scott Diehl, Dieter Van Melkebeek, 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

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

Recommendations

• An improved time-space lower bound for tautologies
• Time-space lower bounds for satisfiability
• Inductive time-space lower bounds for SAT and related problems
• Time-space tradeoffs for satisfiability
• A time lower bound for satisfiability

Cites work

• A survey of lower bounds for satisfiability and related problems.
• Relationships between nondeterministic and deterministic tape complexities
• Time-space lower bounds for satisfiability
• Time-space tradeoffs for counting NP solutions modulo integers
• Time-space tradeoffs for satisfiability

Cited in

(4)

• A nonasymptotic lower time bound for a strictly bounded second-order arithmetic
• scientific article; zbMATH DE number 3906484 (Why is no real title available?)
• scientific article; zbMATH DE number 3952007 (Why is no real title available?)
• An improved time-space lower bound for tautologies

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

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