Threshold Circuits of Small Majority-Depth
Threshold Circuits of Small Majority-Depth
复制标题
小多数深度的阈值电路
DOI：
10.1006/inco.1998.2732
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
D. Thérien
中科院分区：
文献类型：
--
作者：
Alexis Maciel;D. Thérien
我们研究了使用恒定深度阈值电路的计算的复杂性。这样的电路由确定其输入之和是否大于一定阈值的门组成。当仅限于多项式大小时，这些电路会精确计算TC $ \ sp0 $类中的功能。
这些电路通常是通过测量其总深度效率来研究的。使用此观点，最佳的划分和迭代乘法电路分别具有深度三和四。
在本文中，我们提出了另一种方法。由于阈值门比和门更强大，因此我们允许明确使用和门，并认为复杂性的主要度量是电路的大多数，即任何路径上的最大阈值门数在电路中。使用这种方法，我们获得了总深度四和第五的划分和迭代乘法电路，但多数二和三。
所使用的技术称为中国剩余。我们将该技术作为用于计算整数值函数的通用工具，并使用它来获得深度四个阈值电路的多数深度两个，以解决其他算术问题，例如对数和功率序列近似。我们还考虑了整数Modulo Q和有限字段的迭代乘法问题。
多数族裔的概念自然会导致TC $ \ sp0 $的子类的层次结构。我们研究了这个层次结构，并表明它与通常的深度层次结构密切相关。
We investigate the complexity of computations with constant-depth threshold circuits. Such circuits are composed of gates that determine if the sum of their inputs is greater than a certain threshold. When restricted to polynomial size, these circuits compute exactly the functions in the class TC$\sp0$.
These circuits are usually studied by measuring their efficiency in terms of their total depth. Using this point of view, the best division and iterated multiplication circuits have depth three and four, respectively.
In this thesis, we propose a different approach. Since threshold gates are much more powerful than AND-OR gates, we allow the explicit use of AND-OR gates and consider the main measure of complexity to be the majority-depth of the circuit, i.e. the maximum number of threshold gates on any path in the circuit. Using this approach, we obtain division and iterated multiplication circuits of total depth four and five, but of majority-depth two and three.
The technique used is called Chinese remaindering. We present this technique as a general tool for computing functions with integer values and use it to obtain depth-four threshold circuits of majority-depth two for other arithmetic problems such as the logarithm and power series approximation. We also consider the iterated multiplication problem for integers modulo q and for finite fields.
The notion of majority-depth naturally leads to a hierarchy of subclasses of TC$\sp0$. We investigate this hierarchy and show that it is closely related to the usual depth hierarchy.