Time-space lower bounds for SAT on uniform and non-uniform machines
Iannis Tourlakis · 2002
The arguments used by R. Kannan (1984), L. Fortnow (1997), and Lipton-Viglas (1999) are generalized and combined with a new 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 non-uniform machines. In particular we show that for any a 0 and any /spl epsiv/0 and all rationals r/spl ges/1, DTISP(n/sup r/, n/sup l-/spl epsiv//)/spl sub//spl ne/NTIM E(n/sup r/). We show how extending our uniform separations can lead to a separation of SC and NP.