An improved time-space lower bound for tautologies

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

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

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?)
• Alternation-trading proofs, linear programming, and lower bounds (extended abstract)

Cited In (4)

• Title not available (Why is that?)
• Unifying known lower bounds via geometric complexity theory
• An Improved Time-Space Lower Bound for Tautologies
• 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)