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 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.