On the complexity of SAT
On the complexity of SAT
复制标题
论SAT的复杂性
DOI：
10.1109/sffcs.1999.814618
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
Anastasios Viglas
中科院分区：
文献类型：
--
作者：
R. Lipton;Anastasios Viglas
证明了对于任意/spl epsiv/>；0，非确定时间NTIME(N)不包含在确定时间n/sup 2-/spl epsiv//和多对数空间中。这意味着(无限经常)，可满足性不能在时间O(n/sup 2-/spl epsiv//)和多对数空间中求解。对于均匀电路也给出了类似的结果：计算多对数宽度可满足性的对数空间均匀电路需要无限多个几乎二次的大小。
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.