Inductive time-space lower bounds for SAT and related problems

DOI10.1007/s00037-007-0221-1zbMath1125.68060OpenAlexW2023694859MaRDI QIDQ2460033

R. Ryan Williams

Publication date: 14 November 2007

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-007-0221-1

zbMATH Keywords

lower boundsdiagonalizationsatisfiabilitypolynomial-time hierarchybounded nondeterminismTime-space tradeoffs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

Limits on alternation trading proofs for time-space lower bounds ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unifying known lower bounds via geometric complexity theory

This page was built for publication: Inductive time-space lower bounds for SAT and related problems