A Time Lower Bound for Satisfiability Download as PS


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))1/2. 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.