Amplifying Lower Bounds by Means of Self-Reducibility
Amplifying Lower Bounds by Means of Self-Reducibility
复制标题
通过自还原性放大下界
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
M. Koucký
中科院分区：
文献类型：
--
作者：
Eric Allender;M. Koucký
我们观察到，许多重要的计算问题在NC<sup>1</sup>共享一个简单的自归约属性。然后，我们表明，对于任何问题A具有这种自归约属性，A有多项式大小的TC<sup>0</sup>电路当且仅当它有TC<sup>0</sup>电路的大小为<sup>n1 +isin的</sup>每个isin>0（计数的电线的数量在电路的大小电路）。作为这个观察结果的一个例子，考虑布尔公式求值问题（BFE），它对于NC<sup>1</sup>是完全的。从Impagliazzo，Paturi和Saks的下界可以看出，BFE需要深度为d的TC<sup>0</sup>电路，其大小为n<sup>1+isin</sup><sup>d</sup>。如果能够改进该下限以表明存在某个常数isin>0，使得识别BFE的每个TC<sup>0</sup>电路家族具有大小n<sup>1+isin</sup>，则可以得出TC<sup>0</sup> neNC<sup>1</sup>。我们还表明，小均匀恒定深度电路的问题，同时具有小的空间和时间界限的算法。然后，我们利用已知的时间-空间折衷下界来表明，SAT需要均匀深度dTC<sup>0</sup>和AC<sup>0</sup> [6]的大小为<sup>n1 +c的</sup>电路，对于一些常数c取决于d。
We observe that many important computational problems in NC<sup>1</sup> share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial size TC<sup>0</sup> circuits if and only if it has TC<sup>0</sup> circuits of size n<sup>1+isin</sup> for every isin>0 (counting the number of wires in a circuit as the size of the circuit). As an example of what this observation yields, consider the Boolean formula evaluation problem (BFE), which is complete for NC<sup>1</sup>. It follows from a lower bound of Impagliazzo, Paturi, and Saks, that BFE requires depth d TC<sup>0</sup> circuits of size n<sup>1+isin</sup> <sup>d</sup>. If one were able to improve this lower bound to show that there is some constant isin>0 such that every TC<sup>0</sup> circuit family recognizing BFE has size n<sup>1+isin</sup>, then it would follow that TC<sup>0</sup>neNC<sup>1</sup>. We also show that problems with small uniform constant- depth circuits have algorithms that simultaneously have small space and time bounds. We then make use of known time-space tradeoff lower bounds to show that SAT requires uniform depth d TC<sup>0</sup> and AC<sup>0</sup> [6] circuits of size n<sup>1+c</sup> for some constant c depending on d.