In:
Journal of the ACM, Association for Computing Machinery (ACM), Vol. 52, No. 6 ( 2005-11), p. 835-865
Abstract:
We establish the first polynomial time-space lower bounds for satisfiability on general models of computation. We show that for any constant c less than the golden ratio there exists a positive constant d such that no deterministic random-access Turing machine can solve satisfiability in time n c and space n d , where d approaches 1 when c does. On conondeterministic instead of deterministic machines, we prove the same for any constant c less than √2.Our lower bounds apply to nondeterministic linear time and almost all natural NP-complete problems known. In fact, they even apply to the class of languages that can be solved on a nondeterministic machine in linear time and space n 1/c .Our proofs follow the paradigm of indirect diagonalization. We also use that paradigm to prove time-space lower bounds for languages higher up in the polynomial-time hierarchy.
Type of Medium:
Online Resource
ISSN:
0004-5411
,
1557-735X
DOI:
10.1145/1101821.1101822
Language:
English
Publisher:
Association for Computing Machinery (ACM)
Publication Date:
2005
detail.hit.zdb_id:
2006500-0
detail.hit.zdb_id:
6759-3
Bookmarklink