Time-space lower bounds for satistiability

We establish the first polynomial time-space lower bounds for satisfiability on general models of computation. We show that for any constant c less than the golden ratio there exists a positive constant d such that no deterministic random-access Turing machine can solve satisfiability in time n(c) and space n(d), where d approaches 1 when c does. On conondeterministic instead of deterministic machines, we prove the same for any constant c less than root 2. Our lower bounds apply to nondeterministic linear time and almost all natural NP-complete problems known. In fact, they even apply to the class of languages that can be solved on a nondeterministic machine in linear time and space n(1/c). Our proofs follow the paradigm of indirect diagonalization. We also use that paradigm to prove time-space lower bounds for languages higher up in the polynomial-time hierarchy.