Databases Reference
In-Depth Information
examples is succinctness of various formalisms for computing Boolean functions
such as propositional formulas, branching programs and circuits, which has been
investigated since Shannon's seminal work of 1949 [65], where he suggested the
size of the smallest circuit computing a Boolean function as a measure of the
complexity of that function.
We remind the reader (see, e.g., [3,29] for more details) that an
n-ary Boolean
function
,for
n
n
≥
1, is a function
f
:
{
0
,
1
}
→{
0
,
1
}
.An
n
-
input Boolean circuit
,
C
1, is a directed acyclic graph with
n sources
(inputs) and one
sink
(output). Every non-source vertex of
,for
n
≥
C
is called a
gate
; it is labelled with either
∧
or
∨
, in which case it has two incoming edges, or with
¬
, in which case there
is one incoming edge. The number of vertices in
.We
think of a
Boolean formula
as a circuit in which every gate has at most one
outgoing edge. If
C
will be denoted by
|
C
|
n
,then
x
∈{
0
,
1
}
C
(
x
)isthe
output
of
C
on input
x
.Wesay
n
.
In the circuit complexity theory, we are interested in
families of Boolean func-
tions
, that is, sequences
f
1
,f
2
,...
,whereeach
f
n
is an
n
-ary Boolean function.
For example, we can consider the family
that
C
computes
a Boolean function
f
if
C
(
x
)=
f
(
x
), for every
x
∈{
0
,
1
}
Clique
n,k
(
e
) of Boolean functions of
j<j
≤
n
(
n
−
1)
/
2variables
e
jj
,1
≤
n
, that return 1 iff the graph with vertices
j, j
}|
{
1
,...,n
}
and edges
{{
e
jj
=1
}
contains a
k
-clique, for some fixed
k
.
Given a function
T
:
N
→
N
,bya
T-size family of circuits
we mean a sequence
1
,
2
,...
,whereeach
n
is an
n
-input Boolean circuits of size
n
C
T
(
n
).
Every family
f
n
of Boolean functions can clearly be computed by circuits of size
n
C
C
|
C
|≤
2
n
(take disjunctive normal forms representing the
f
n
). The class of languages
that are decidable by families of
polynomial-size
circuits is denoted by
·
P
/poly.
It is known that
by
showing that
NP
⊆
P
/
poly. In other words, to crack one of the most important
problems in computer science and mathematics,
1
it is enough to find a family of
Boolean functions in
NP
that cannot be computed by a polynomial-size family
of circuits. This does not look like a particularly hard problem! After all, it
has been known since 1949 that the majority of Boolean functions can only be
computed by exponential-size circuits. Yet, so far no one has managed to find a
concrete family of functions in
P P
/
poly. Thus, one might hope to prove that
P
=
NP
NP
that need circuits with more than 4
.
5
n
−
o
(
n
)
gates [40].
Investigating
restricted
classes of Boolean circuits has proved to be much more
successful. The class that is relevant in the context of PE-rewritings consists of
monotone
Boolean functions, that is, those computable by
monotone circuits
with only
∧
-and
∨
-gates. For example, the function
Clique
n,k
(
e
) is mono-
tone. As
Clique
n,k
can be
computed by polynomial-size circuits is equivalent to the open
Clique
n,k
is
NP
-complete, the question whether
/
poly
problem. A series of papers, started by Razborov's [57], gave an exponential
lower bound for the size of
monotone
circuits computing
NP
⊆
P
Clique
n,k
:2
Ω
(
√
k
)
for
4
(
n/
log
n
)
2
/
3
[2]. For monotone formulas, an even better lower bound was
obtained: 2
Ω
(
k
)
for
k
=2
n/
3 [56]. It follows that, if we assume
1
k
≤
NP
⊆
P
/
poly,
1
It is actually one of the seven Millennium Prize Problems worth of $1 000 000 each;
