An improved time-space lower bound for tautologies

DOI10.1007/S10878-009-9286-XzbMATH Open1229.90158OpenAlexW2069877939MaRDI QIDQ652633FDOQ652633

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

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

zbMATH Keywords

computational complexitysatisfiabilitytautologiestime-space lower bounds

Mathematics Subject Classification ID

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

Cites Work

• Relationships between nondeterministic and deterministic tape complexities
• Time-space tradeoffs for satisfiability
• Time-space lower bounds for satisfiability
• A Survey of Lower Bounds for Satisfiability and Related Problems
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (3)

• Title not available (Why is that?)
• Unifying known lower bounds via geometric complexity theory
• Title not available (Why is that?)

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)