Limiting Negations in Formulas
Limiting Negations in Formulas
复制标题
DOI：
10.1007/978-3-642-02927-1_58
复制
发表时间：
2009-07
期刊：
影响因子：
--
通讯作者：
Hiroki Morizumi
中科院分区：
文献类型：
--
作者：
Hiroki Morizumi
负限电路是介于一般电路和单调电路之间的一种电路模型。本文考虑公式中的极限否定。在一个布尔电路中，计算布尔函数f的最少非门数称为求逆复杂度。1958年，Markov确定了所有布尔函数的求逆复杂度，并特别证明了log 2（n+ 1）个非门足以计算n个变量的布尔函数。我们确定公式中每个布尔函数的反演复杂度，即，讨论了计算（表示）一个布尔函数的布尔公式中的最少非门（非运算符）数，特别证明了n/2个非门足以计算n个变量的布尔函数。此外，我们证明，如果有一个多项式大小的公式计算布尔函数f，那么有一个多项式大小的公式计算f与最多<$n/2个非门。本文还讨论了求反范式公式的求反复杂性，证明了对任意n元布尔函数，求反复杂性至多为n的多项式。
Negation-limited circuits have been studied as a circuit model between general circuits and monotone circuits. In this paper, we consider limiting negations in formulas. The minimum number of NOT gates in a Boolean circuit computing a Boolean functionfis called the inversion complexity off. In 1958, Markov determined the inversion complexity of every Boolean function and particularly proved that ⌈log2(n+ 1) ⌉ NOT gates are sufficient to compute any Boolean function onnvariables. We determine the inversion complexity of every Boolean function in formulas, i.e., the minimum number of NOT gates (NOT operators) in a Boolean formula computing (representing) a Boolean function, and particularly prove that ⌈n/2 ⌉ NOT gates are sufficient to compute any Boolean function onnvariables. Moreover we show that if there is a polynomial-size formula computing a Boolean functionf, then there is a polynomial-size formula computingfwith at most ⌈n/2 ⌉ NOT gates. We consider also the inversion complexity in formulas of negation normal form and prove that the inversion complexity is at most polynomials ofnfor every Boolean function onnvariables.