数理解析研究所講究録
第 1799 巻 2012 年 81-83

81

Limiting Negations in Probabilistic Circuits
Hiroki Morizumi
Interdisciplinary Faculty of Science and Engineering, Shimane University
morizumi@cis.shimane-u.ac.jp

Abstract

The minimum number of NOT gates in a Boolean circuit computing
a Boolean function is called the inversion complexity of . In 1958,
Markov determined the inversion complexity of every Boolean function
and particularly proved thatNOT gates are sufficient tocompute any Boolean function on variables. In this note, we consider
circuits computing probabilistically, and prove that the decrease ofthe inversion complexity is at most a constant if probabilistic circuits
compute a correct value with probability $1/2+p$ for some constant$p>0$ .
$f$$f\cdot$$\lceil\log_{2}(n+1)\rceil$$n$1Introduction

When we consider Boolean circuits with a limited number of NOT gates,
there is a basic question: Can a given Boolean fumction be computed by acircuit with a $1i_{1}nited$ number of NOT gates? This question was answered byMarkov [2] in 1958 and theplays an important role in the study of thenegation-limited circuit complexity. The inversion complexity of a Booleanfunction is the minuimum number of NOT gates required to construct a
Boolean circuit computing , and Markov completely determined the inversion complexity of every Boolean function . In particular, it has beenshown thatNOT gates are sufficient to compute any Booleanfunction.
The inversion complexity has been studied for many circuit models suchas constant depth circuit [5], bounded depth circuits [6], formulas [3], bounded
treewidth and upward planar circuits [1], and non-deterministic circuits [4].
In this note, we consider the inversion complexity in probabilistic circuits.
$res\iota ilt$

$f$

$f$

$f$

$\lceil\log_{2}(n+1)\rceil$2

Preliminaries

A circuit is an acyclic Boolean circuit which consists of AND gates of fanin two, OR gates of fan-in two and NOT gates. A probabilistic circuit isa circuit with actual inputs $(x_{1}, \ldots,x_{n})\in\{0,1\}^{n}$ and some further inputs

82
called random inputs which take the values and 1
independently with probability 1/2. For $0<p\leq 1/2$ , a probabilistic circuit$C(x)$ computes a Boolean fUnction $f(x)$ with probability $1/2+p$ if$0$$(r_{1}, \ldots, r_{m})\in\{0,1\}^{m}$

Prob $[C(x)=f(x)]\geq 1/2+p$ for each $x\in\{0,1\}^{n}$ .
In this note, we call a circuit without random inputs a deterministic circuit
to distinguish it from a probabilistic circuit.
for all
Let and $x’$ be Boolean vectors in $\{0,1\}^{n}$ . $x\leq x’$ means$1\leq i\leq n$ . $x<x’$ means
for some .
andThe theorem of Markov [2] is in the following. We denote the inversion
complexity of a Boolean function in deterministic circuits by $I(f)$ . A chain
is an increasing sequence $x^{1}<x^{2}<\cdots<x^{k}$ of Boolean vectors in $\{0,1\}^{n}$ .
The decrease $d_{X}(f)$ of a Boolean function on a chain $X$ is the number ofindices such that $f(x^{i})\not\leq f(x^{i+1})$ . The decrease $d(f)$ of is the maximumof $d_{X}(f)$ over all increasing sequences $X$ . Markov gave the tight bound of
the inversion complexity for every Boolean function.
$x_{i}\leq x_{i}^{l}$$x$$x\leq x^{l}$$i$$x_{i}<x_{i}’$

$f$

$f$

$f$

$i$

Theorem 1 (Markov[2]). For every Boolean function ,$f$

$I(f)=\lceil\log_{2}(d(f)+1)\rceil$

In Theorem 1, the Boolean function$f$.

can also be a multi-output function.

3

Inversion Complexity in Probabilistic Circuits

3.1

ResultWe denote by $I_{pc}(f, q)$ the inversion complexity of a Boolean functionin probabilistic circuits with probability . We consider only single-output
Boolean functions since probabilistic circuits are not defined as ones computing multi-output Boolean functions.
$f$

$q$

Theorem 2. For every Boolean fun ction ,$f$$I_{pc}(f, 1/2+p)\geq\lceil\log_{2}(2p\cdot d(f)+1)\rceil$.

By Theorem 1 and Theorem 2, if is a constant, then the decrease of
the inversion complexity from deterministic circuits is at most a constant,which means that probabihstic computation save only the constant numberof NOT gates. Especially, if $p=1/4$ , then,$p$Corollary 1. For every Boolean function ,$f$$I_{pc}(f, 3/4)\geq I(f)-1$.

83
3.2

Proof

Proof (of Theorem 2). Let

be a probabilistic circuit computes
withprobability $1/2+p$ , and let $X$ be a chain such that $d_{X}(f)=d(f)$ , i.e., thedecrease of is the maximum on $X$ . Consider some such that $f(x^{i})=1$and $f(x^{i+1})=0$ . Since computes each ofand $f(x^{i+1})$ correctly with$2^{nz}(1/2+p)$
at least
random inputs, the number of random inputs such thatcomputes both of $f(x^{i})=1$ and $f(x^{i+1})=0$ correctly is at least,$C$$f$$f$$i$$C$$f(x^{i})$$C$$2^{m}\cdot(1-2\cdot(1-(1/2+p)))=2^{m}\cdot 2p$.

Since, for all such that $f(x^{i})=1$ and $f(x^{i+1})=0$ , the number of random
inputs such that computes both of $f(x^{i})=1$ and $f(x^{i+1})=0$ correctly isat least, there is random inputs such that with computes $f(x^{i})=$and $f(x^{i+1})=0$ correctly for at least $2p\cdot d(f)i’ s$ . Let $C’$ be a circuit
which obtained by fixing random inputs in to . C’ is a deterininistic
circuit and computes a Boolean $f\iota mctionf’$ such that $d(f’)\geq 2p\cdot d(f)$ . By
Theorem 1, $C’$ includes at least
NOT gates, which isalso included in C.
口$i$$C$$2^{m}\cdot 2p$$C$$r$$r$$1$$C$$r$$\lceil\log_{2}(2p\cdot d(f)+1)\rceil$

References[1] J. He, H. Liang and J.M.N. Sarma, Lilnitilig negations in bounded
treewidth and upward planar circ, Proc. of 35th MFCS, LNCS
vol. 6281, pp. 417-428, 2010.
$\iota\iota its$

[2] A.A. Markov, On the inversion complexity of a system of functions, J.
ACM 5(4), pp. 331-334, 1958.
[3] H. Morizumi, Limiting negations in formulas, Proc. of 36th ICALP,LNCS vol. 5555, pp. 701-712, 2009.
[4] H. Morizumi, Lilniting negations in non-deterininistic circuits, Theoret.
Comput. Sci. 410(38-40), pp. 3988-3994, 2009.
[5] M. Santha and C. Wilson, Limiting negations in constant depth circuits,
SIAM J. Comput. 22(2), pp. 294-302, 1993.
[6] S. Sung and K. Tanaka, Limiting negations in bounded-depth cir: an extension of Markovs theorem, Proc. of 14th ISAAC, LNCS
vol. 2906, pp. 108-116, 2003.
$c\iota\iota its$