Name
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 nc and space nd, where d approaches 1 when c does. On conondeterministic instead of deterministic machines, we prove the same for any constant c less than &2radic;.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 n1/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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1145/1101821.1101822 | J. ACM |
Keywords | Field | DocType |
constant c,nondeterministic machine,deterministic random-access Turing machine,polynomial time-space,time nc,time-space lower bounds,space nd,deterministic machine,linear time,space n1,lower bound,complexity of satisfiability,Time-space lower bound | Discrete mathematics,Time space,Combinatorics,Existential quantification,Polynomial,Computer science,Satisfiability,Golden ratio,Model of computation | Journal |
Volume | Issue | ISSN |
52 | 6 | 0004-5411 |
Citations | PageRank | References |
30 | 1.01 | 19 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lance Fortnow | 1 | 2788 | 352.32 |
| Richard J. Lipton | 2 | 6412 | 1796.57 |
| Dieter van Melkebeek | 3 | 487 | 32.80 |
| Anastasios Viglas | 4 | 197 | 15.97 |