Abstract

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 b for some positive constant b. Our techniques allow us to establish this result for b < 1 Electronic Colloquium on Computational Complexity, Report No. 28 (2000) 2 ( a+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 the first nontrivial lower bounds for nondeterministic linear time machines using sublinear space. For example, there exists a language computable in nondeterministic linear time and n.619 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 lineartime Σℓ-computations require essentially n ℓ time if we only allow n o(1) space. We also show new lower bounds on conondeterministic versus nondeterministic computation. ISSN 1433-8092