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.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computer Science(all)
- Computational complexity
- Lower bounds