On the complexity of SAT

We show that non-deterministic time NTIME(n) is not contained in deterministic time n^2-ε and polylogarithmic space, for any ε>0. This implies that (infinitely often), satisfiability cannot be solved in time O(n^2-ε) 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