Lower bounds on the complexity of recognizing SAT by Turing machines

DOI10.1016/S0020-0190(00)00227-1zbMath1032.68661MaRDI QIDQ1603493

Rahul Santhanam

Publication date: 14 July 2002

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

SatisfiabilityComputational complexityTime-space tradeoffs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (2)

Effective guessing has unlikely consequences ⋮ Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle

Cites Work

• Unnamed Item
• Unnamed Item
• Two time-space tradeoffs for element distinctness
• A time-space tradeoff for language recognition
• Towards separating nondeterminism from determinism
• Nondeterministic linear-time tasks may require substantially nonlinear deterministic time in the case of sublinear work space
• Near-Optimal Time-Space Tradeoff for Element Distinctness

This page was built for publication: Lower bounds on the complexity of recognizing SAT by Turing machines