Time–Space Tradeoffs for SAT on Nonuniform Machines

AbstractThe arguments used by R. Kannan (1984, Math. Systems Theory17, 29–45), L. Fortnow (1997, in “Proceedings, Twelfth Annual IEEE Conference on Computational Complexity, Ulm, Germany, 24–27 June, 1997,” pp. 52–60), and R. J. Lipton and A. Viglas (1999, in “40th Annual Symposium on Foundations of Computer Science, New York, 17–19 Oct. 1999,” pp. 459–469) are generalized and combined with an argument for diagonalizing over machines taking n bits of advice on inputs of length n to obtain the first nontrivial time–space lower bounds for SAT on nonuniform machines. In particular, we show that for any a<2 and any ε>0, SAT cannot be computed by a random access deterministic Turing machine using na time, no(1) space, and o(n2/2−ε) advice nor by a random access deterministic Turing machine using n1+o(1) time, n1−ε space, and n1−ε advice. More generally, we show that if for some ε>0 there exists a random access deterministic Turing machine solving SAT using na time, nb space, and o(n(a+b)/2−ε) advice, then a⩾12(b2+8−b). Lower bounds for computing \overline{{\bfSAT}} on random access nondeterministic Turing machines taking sublinear advice are also obtained. Moreover, we show that SAT does not have NC1 circuits of size nl+o(1) generated by a nondeterministic log–space machine taking no(1) advice. Additionally, new separations of uniform classes are obtained. We show that for all ε>0 and all rational numbers r⩾1, DTISP(nr, n1−ε) is properly contained in NTIME(nr)