Limiting Negations in Probabilistic Circuits (New Trends in Algorithms and Theory of Computation)
Limiting Negations in Probabilistic Circuits (New Trends in Algorithms and Theory of Computation)
复制标题
概率电路中的限制否定（算法和计算理论的新趋势）
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Hiroki Morizumi
中科院分区：
文献类型：
--
作者：
Hiroki Morizumi
在一个布尔电路中计算布尔函数$f$的最小非门数称为$f \cdot$的求逆复杂度。1958年，马尔可夫确定了每个布尔函数的反演复杂度，并特别证明了$ \lceil\log_{2}（n+1）\rceil$ NOT门足以计算$n$个变量的任何布尔函数。在本文中，我们考虑电路的概率计算，并证明如果概率电路以概率$1/2+p$计算出正确值，并且对于某个常数$p >0$，则求逆复杂度的降低最多是一个常数。
The minimum number of NOT gates in a Boolean circuit computing a Boolean function $f$ is called the inversion complexity of $f \cdot$ . In 1958, Markov determined the inversion complexity of every Boolean function and particularly proved that $ \lceil\log_{2}(n+1)\rceil$ NOT gates are sufficient to compute any Boolean function on $n$ variables. In this note, we consider circuits computing probabilistically, and prove that the decrease of the inversion complexity is at most a constant if probabilistic circuits compute a correct value with probability $1/2+p$ for some constant $p >0$ .