An improved time-space lower bound for tautologies

DOI10.1007/s10878-009-9286-xzbMath1229.90158OpenAlexW2069877939MaRDI QIDQ652633

Dieter van Melkebeek, Scott Diehl, R. 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

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

Related Items (1)

Unifying known lower bounds via geometric complexity theory

Cites Work

• 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
• Unnamed Item
• Unnamed Item

This page was built for publication: An improved time-space lower bound for tautologies