Local Reductions
Local Reductions
复制标题
当地折扣
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Emanuele Viola
中科院分区：
文献类型：
--
作者：
Hamidreza Jahanjou;Eric Miles;Emanuele Viola
我们将不确定时间T ≥ 2n简化为一个3SAT的准线性大小的实例φ| φ| = T · log T，使得存在显式电路C，在输入时，log的索引i| φ| bits输出第i个子句，C的每个输出位依赖于O（1）个输入位。之前的最好成绩是NC 1中的C。即使在多项式大小的简单设置中|φ| = poly（T）之前的最佳结果是AC 0中的C。更一般地，对于任何时间T ≥ n且参数r ≤ n，我们得到log 2| φ| = max（log T，n/r）+O（log n）+O（log log T）并且C的每个输出位是决策树
We reduce non-deterministic time T ≥ 2n to a 3SAT instance φ of quasilinear size |φ| = T · log T such that there is an explicit circuit C that on input an index i of log |φ| bits outputs the ith clause, and each output bit of C depends on O(1) input bits. The previous best result was C in NC1. Even in the simpler setting of polynomial size |φ| = poly(T ) the previous best result was C in AC0. More generally, for any time T ≥ n and parameter r ≤ n we obtain log2 |φ| = max(log T, n/r)+O(log n)+O(log log T ) and each output bit of C is a decision tree of