Lower bounds on the complexity of recognizing SAT by Turing machines
type: Item
instance of: scholarly article
title: Lower bounds on the complexity of recognizing SAT by Turing machines
zbMATH Open document ID: 1032.68661
DOI: 10.1016/S0020-0190(00)00227-1
published in: Information Processing Letters
publication date: 2002-07-14T00:00:00Z
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1767386
zbMATH Keywords: Computational complexity
zbMATH Keywords: Time-space tradeoffs
zbMATH Keywords: Satisfiability
author: Rahul Santhanam
MaRDI profile type: Publication
cites work: A time-space tradeoff for language recognition
cites work: Q4234060
cites work: Q3826533
cites work: Nondeterministic linear-time tasks may require substantially nonlinear deterministic time in the case of sublinear work space
cites work: Towards separating nondeterminism from determinism
cites work: Two time-space tradeoffs for element distinctness
cites work: Near-Optimal Time-Space Tradeoff for Element Distinctness
description: scientific article; zbMATH DE number 1767386