Time-space tradeoffs for nondeterministic computation

We show new tradeoffs for satisfiability and nondeterministic linear time. Satisfiability cannot be solved on general purpose random-access Turing machines in time n^1.618 and space n^o(1). This improves recent results of Fortnow and of Lipton and Viglas. In general, for any constant a less than the golden ratio, we prove that satisfiability cannot be solved in time n^a and space n^δ for some positive constant b. Our techniques allow us to establish this result for b<½(α+2/a(2)-a). We can do better for a close to the golden ratio, for example, satisfiability cannot be solved by a random-access Turing machine using n^1.46 time and n^.11 space. We also show tradeoffs for nondeterministic linear time computations using sublinear space. For example, there exists a language computable in nondeterministic linear time and n⁶¹⁹ space that cannot be computed in deterministic n^1.618 time and n^o(1) space. Higher up the polynomial-time hierarchy we can get better bounds. We show that linear-time Σ_l-computations require essentially n^l time on deterministic machines that use only n^o(1) space. We also show new lower bounds on conondeterministic versus nondeterministic computation