We show new lower bounds for satisfiability and nondeterministic linear time. Satisfiability cannot be solved on general purpose random-access Turing machines in time n1.618 and space no(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 na and space nb for some positive constant b. Our techniques allow us to establish this result for b < ((a+2)/a2-a)/2. We can do better for a close to the golden ratio, for example, satisfiability cannot be solved by a random-access Turing machine using n1.46 time and n.11 space. We also show the first nontrivial lower bounds on 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 n1.618 time and no(1) space.
Higher up the polynomial-time hierarchy we can get better bounds. We show that linear-time alternating computations with a most k alternations require essentially nk time if we only allow no(1) space. We also show new lower bounds on conondeterministic versus nondeterministic computation.
DIMACS Home Page