Uniform constant-depth threshold circuits for division and iterated multiplication
Uniform constant-depth threshold circuits for division and iterated multiplication
复制标题
DOI：
10.1016/s0022-0000(02)00025-9
复制
发表时间：
2002-12
期刊：
影响因子：
--
通讯作者：
W. Hesse;Eric Allender;D. M. Barrington
中科院分区：
文献类型：
--
作者：
W. Hesse;Eric Allender;D. M. Barrington
自20世纪80年代中期以来，它就被人们所知（SIAM J. Comput. 15（1986）994; SIAM J. 21（1992）896），整数除法可以通过多数门的多时间均匀恒定深度电路来执行;等效地，除法问题在于P-均匀TC 0。最近，这被改进为L-均匀TC 0（RAIRO Theoret. Inform. 35（2001）259），但是仍然不知道除法是否可以由DLOGTIME均匀TC 0电路执行。DLOGTIME一致性条件被许多人认为是适用于小电路复杂性类别（如TC 0）的最自然的一致性概念; DLOGTIME一致性TC 0也被称为FOM，因为它对应于有限模型理论中具有多数量词的一阶逻辑。除法是已知属于P-均匀电路复杂度类的自然问题的突出例子，但不知道是否属于DLOGTIME-均匀版本。我们表明，确实司是在DLOGTIME均匀的TC 0。首先，我们表明，司在于复杂性类FOM+POW通过增强FOM与一个谓词为幂模小素数。然后，我们表明，谓词POW本身在于FOM。(In事实上，它位于FO或DLOGTIME-均匀AC 0中。）除法及相关问题的快速并行计算的基本思想是中国余数表示（CRR）-以余数模许多小素数的形式存储一个数。CRR操作可以在日志空间中执行，这一事实对小空间类有着有趣的影响。对于s（n）=o（log n），我们定义了两个版本的s（n）空间：dspace（s（n））作为传统版本，其中工作带开始为空白，而DSPACE（s（n））在计算开始之前通过结束标记建立空间边界。我们提出了一个新的翻译引理表征DSPACE类中的一元语言。这是已知的（理论计算。Sci. 3（1976）213）证明{0 n：n是素数}空间（log log n）。我们证明，如果这可以改进为{0 n：n is prime} DSPACE（log log n），则L NP。
It has been known since the mid-1980s (SIAM J. Comput. 15 (1986) 994; SIAM J. Comput. 21 (1992) 896) that integer division can be performed by poly-time uniform constant-depth circuits of Majority gates; equivalently, the division problem lies in P-uniform TC0. Recently, this was improved to L-uniform TC0(RAIRO Theoret. Inform. Appl. 35 (2001) 259), but it remained unknown whether division can be performed by DLOGTIME-uniform TC0circuits. The DLOGTIME uniformity condition is regarded by many as being the most natural notion of uniformity to apply to small circuit complexity classes such as TC0; DLOGTIME-uniform TC0is also known as FOM, because it corresponds to first-order logic with Majority quantifiers, in the setting of finite model theory. Integer division has been the outstanding example of a natural problem known to be in a P-uniform circuit complexity class, but not known to be in its DLOGTIME-uniform version. We show that indeed division is in DLOGTIME-uniform TC0. First we show that division lies in the complexity class FOM+POW obtained by augmenting FOM with a predicate for powering modulo small primes. Then we show that the predicate POW itself lies in FOM. (In fact, it lies in FO, or DLOGTIME-uniform AC0.) The essential idea in the fast parallel computation of division and related problems is that of Chinese remainder representation (CRR)—storing a number in the form of its residues modulo many small primes. The fact that CRR operations can be carried out in log space has interesting implications for small space classes. We define two versions of s(n) space for s(n)=o( log n) : dspace(s(n)) as the traditional version where the worktape begins blank, and DSPACE(s(n)) where the space bound is established by endmarkers before the computation starts. We present a new translational lemma characterizing the unary languages in the DSPACE classes. It is known (Theoret. Comput. Sci. 3 (1976) 213) that {0n: n is prime} ∉ dspace ( log log n) . We show that if this can be improved to {0n:n is prime} ∉ DSPACE ( log log n) , it follows that L≠NP.