Lower Bounds for the Size of Nondeterministic Circuits
Lower Bounds for the Size of Nondeterministic Circuits
复制标题
非确定性电路尺寸的下界
DOI：
10.1007/978-3-319-21398-9_23
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Hiroki Morizumi
中科院分区：
文献类型：
--
作者：
Hiroki Morizumi;Hiroki Morizumi
非确定性电路是电路复杂性理论中的一种非确定性计算模型。本文证明了计算奇偶函数的非确定电路的规模的一个下界。众所周知，计算奇偶函数的（确定性）电路的最小尺寸正好等于。因此，我们的结果意味着，不确定性计算是无用的计算奇偶函数的电路，不能减少的大小。据我们所知，这是显式布尔函数具有无限非确定性的非确定性电路（包括公式，常数深度电路等）大小的第一个非平凡下界。我们还讨论了一种方法来证明下界的大小确定性电路通过下界的大小不确定性的限制电路。
Nondeterministic circuits are a nondeterministic computation model in circuit complexity theory. In this paper, we prove alower bound for the size of nondeterministic-circuits computing the parity function. It is known that the minimum size of (deterministic)-circuits computing the parity function exactly equals. Thus, our result means that nondeterministic computation is useless to compute the parity function by-circuits and cannot reduce the size from. To the best of our knowledge, this is the first nontrivial lower bound for the size of nondeterministic circuits (including formulas, constant depth circuits, and so on) with unlimited nondeterminism for an explicit Boolean function. We also discuss an approach to proving lower bounds for the size of deterministic circuits via lower bounds for the size of nondeterministic restricted circuits.
登录
查看更多内容
需要 3n 网络大小的布尔函数
DOI：
10.1016/0304-3975(83)90029-4
发表时间：
1984
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
Norbert Blum
通讯作者：
Norbert Blum
仿射分散器电路复杂度的 3n - o(n) 下界的基本证明
DOI：
10.1007/978-3-642-22993-0_25
发表时间：
2011
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Evgeny Demenkov;A. Kulikov
通讯作者：
A. Kulikov
布尔电路的显式下限 4.5n - o(n)
影响因子：
0.9
作者：
Oded Lachish;R. Raz
通讯作者：
R. Raz
布尔电路的显式下界 5n - o(n)
DOI：
--
发表时间：
2002
期刊：
International Symposium on Mathematical Foundations of Computer Science
影响因子：
--
作者：
K. Iwama;Hiroki Morizumi
通讯作者：
Hiroki Morizumi
影响因子：
3.7
作者：
C. Schnorr
通讯作者：
C. Schnorr