Nondeterministic polynomial time versus nondeterministic logarithmic space: time-space tradeoffs for satisfiability

We give the first nontrivial model-independent time-space tradeoffs for satisfiability. Namely, we show that S¯A¯T¯ cannot be solved simultaneously in n¹⁺⁰⁽¹⁾ time and n^1-ε space for any ε>0 on general random-access nondeterministic Turing machines. We also give several other related results. Our proof uses two basic ideas. First we show that if S¯A¯T¯ can be solved nondeterministically with a small amount of space then we can collapse a nonconstant number of levels of the polynomial-time hierarchy. Next we extend work of V. Nepomnjascii (1970) to show that a nondeterministic computation of super linear time and sublinear space can be simulated in alternating linear time. Combining these facts with simple diagonalization yields our main result. We discuss how these bounds lead to a new approach to separating the complexity classes NL and NP. We give some possibilities and limitations of this approach