Circuits and local computation
Circuits and local computation
复制标题
电路和本地计算
DOI：
--
复制
发表时间：
1989
期刊：
影响因子：
--
通讯作者：
A. Yao
中科院分区：
文献类型：
--
作者：
A. Yao
本文共分两个部分。在第一部分中，我们证明了深度为<；italic>；k<；/italic>；的多项式大小单调阈值电路在参数<；italic>；k<；/italic>；中形成了一个适当的层次。这特别意味着单调<；italic>；TC<；/italic>；<；supscrpt>；0<；/supscrpt>；被适当地包含在<；italic>；NC<；/italic>；<；supscrpt>；1<；/supscrpt>；.中在第二部分，我们引入了一个新的概念，称为<；italic>；局部函数<；/italic>；，它试图刻画何时只使用局部处理元素就可以有效地计算函数。它作为一个统一的框架，用于查看相关的结果，有时甚至是明显不相关的结果。特别地，Razborov[Ra1]、Karchmer和Wigderson[KW]关于单调电路下界的最新结果，以及本文第一部分中的一个主要定理，可以被认为是证明某些函数是非局部的。我们还将提出一种基于局部性的方法来破解(非单调)<；italic>；TC<；/italic>；<；supscrpt>；0<；/supscrpt>；适当包含在<；italic>；NC<；/italic>；<；supscrpt>；1<；/supscrpt>；.中的猜想
This paper contains two parts. In Part I, we show that polynomial-size monotone threshold circuits of depth <italic>k</italic> form a proper hierarchy in parameter <italic>k</italic>. This implies in particular that monotone <italic>TC</italic><supscrpt>0</supscrpt> is properly contained in <italic>NC</italic><supscrpt>1</supscrpt>. In Part II, we introduce a new concept, called <italic>local function</italic>, which tries to characterize when a function can be efficiently computed using only localized processing elements. It serves as a unifying framework for viewing related and sometimes apparently unrelated results. In particular, it will be demonstrated that the recent results on lower bounds for monotone circuits by Razborov [Ra1] and Karchmer and Wigderson [KW], as well as a main theorem in Part I of this paper, can be regarded as proving certain functions to be nonlocal. We will also suggest an approach based on locality for attacking the conjecture that (nonmonotone) <italic>TC</italic><supscrpt>0</supscrpt> is properly contained in <italic>NC</italic><supscrpt>1</supscrpt>.