A time lower bound for satisfiability

We show that a deterministic Turing machine with one d-dimensional work tape and random access to the input cannot solve satisfiability in time n a for a < ( d + 2 ) / ( d + 1 ). For conondeterministic machines, we obtain a similar lower bound for any a such that a 3 < 1 + a / ( d + 1 ). The same bounds apply to almost all natural NP -complete problems known.

Authors

• Dieter van Melkebeek
• Ran Raz

Keywords

• Computational complexity
• Lower bounds
• Satisfiability