Abstract
We show that a deterministic Turing machine with one d-dimensional work tape and random access to the input cannot solve satisfiability in time na for a<(d+2)/(d+1). For conondeterministic machines, we obtain a similar lower bound for any a such that a3<1+a/(d+1). The same bounds apply to almost all natural NP-complete problems known.
Original language | English (US) |
---|---|
Pages (from-to) | 311-320 |
Number of pages | 10 |
Journal | Theoretical Computer Science |
Volume | 348 |
Issue number | 2-3 SPEC. ISS. |
DOIs | |
State | Published - Dec 8 2005 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computer Science(all)
Keywords
- Computational complexity
- Lower bounds
- Satisfiability