An improved time-space lower bound for tautologies

DOI10.1007/S10878-009-9286-XMaRDI QIDQ652633zbMATH OpenOpenAlexFDO

Authors Scott Diehl, Dieter Van Melkebeek, Ryan Williams

Publication date 15 December 2011

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-009-9286-x

zbMATH Keywords

computational complexitysatisfiabilitytautologiestime-space lower bounds

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

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
• Time-space tradeoffs for SAT on nonuniform machines

Cites work

• scientific article; zbMATH DE number 1860652 (Why is no real title available?)
• A survey of lower bounds for satisfiability and related problems.
• Alternation-trading proofs, linear programming, and lower bounds (extended abstract)
• Relationships between nondeterministic and deterministic tape complexities
• Time-space lower bounds for satisfiability
• Time-space tradeoffs for satisfiability

Cited in

(4)

• scientific article; zbMATH DE number 3906484 (Why is no real title available?)
• Unifying known lower bounds via geometric complexity theory
• An Improved Time-Space Lower Bound for Tautologies
• scientific article; zbMATH DE number 3952007 (Why is no real title available?)

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 Q652633)