On the complexity of SAT

Abstract

We show that non-deterministic time NTIME(n) is not contained in deterministic time n/sup 2-/spl epsiv// and polylogarithmic space, for any /spl epsiv/>0. This implies that (infinitely often), satisfiability cannot be solved in time O(n/sup 2-/spl epsiv//) and polylogarithmic space. A similar result is presented for uniform circuits; a log-space uniform circuit of polylogarithmic width computing satisfiability requires infinitely often almost quadratic size.