Cryptography Reference
In-Depth Information
is obvious that
poly (in fact, strict containment can be proved by considering
non-recursive unary languages). Furthermore:
P
⊆
P
/
BPP
⊆
P
/
poly
.
Theorem 1.3.7:
Proof:
Let
M
be a probabilistic polynomial-time Turing machine recognizing
L
∈
BPP
. Let
χ
L
(
x
)
def
=
1if
x
∈
L
, and
χ
L
(
x
)
def
=
0 otherwise. Then, for every
x
∈{
0
,
1
}
∗
,
2
3
Assume, without loss of generality, that on each input of length
n
, machine
M
uses the same number, denoted
m
=
poly(
n
), of coin tosses. Let
x
∈{
0
,
1
}
Pr
[
M
(
x
)
=
χ
L
(
x
)]
≥
n
.
Clearly, we can find for each
x
∈{
,
}
n
a sequence of coin tosses
r
∈{
,
}
m
0
1
0
1
=
χ
L
(
x
) (in fact, most sequences
r
have this property). But can
one sequence
r
∈{
such that
M
r
(
x
)
0
,
1
}
m
fit all
x
∈{
0
,
1
}
n
? Probably not. (Provide an example!)
2
Nevertheless, we can find a sequence
r
3
of all the
x
's of length
n
. This is done by an averaging argument (which asserts that if
∈{
0
,
1
}
n
that fits
2
3
of the
r
's are
2
3
good for each
x
, then there is an
r
that is good for at least
of the
x
's). However,
this does not give us an
r
that is good for all
x
n
. To get such an
r
,wehave
to apply the preceding argument on a machine
M
with exponentially vanishing
error probability. Such a machine is guaranteed by Exercise 5. Namely, for every
x
∈{
0
,
1
}
}
∗
,
∈{
0
,
1
[
M
(
x
)
2
−|
x
|
Pr
=
χ
L
(
x
)]
>
1
−
Applying the averaging argument, now we conclude that there exists an
r
∈
{
0
,
1
}
m
, denoted
r
n
, that is good for
more than
a1
−
2
−
n
fraction of the
x
's
n
. It follows that
r
n
is good for all the 2
n
inputs of length
n
.
Machine
M
(viewed as a deterministic two-input machine), together with the
infinite sequence
r
1
,
r
2
,...
constructed as before, demonstrates that
L
is in
P
/
poly.
in
{
0
,
1
}
Non-Uniform Circuit Families.
A more convenient way of viewing non-uniform poly-
nomial time, which is actually the way used in this topic, is via (non-uniform) families
of polynomial-size Boolean circuits. A
Boolean circuit
is a directed acyclic graph with
internal nodes marked by elements of
{∧
,
∨
,
¬}
. Nodes with no in-going edges are
called
input nodes
, and nodes with no out-going edges are called
output nodes
. A node
marked
¬
can have only one child. Computation in the circuit begins with placing input
bits on the input nodes (one bit per node) and proceeds as follows. If the children of a
node (of in-degree
d
) marked
∧
have values
v
1
,v
2
,...,v
d
, then the node gets the value
∧
d
i
=
1
v
i
. Similarly for nodes marked
∨
¬
. The output of the circuit is read from its
output nodes. The
size
of a circuit is the number of its edges. A
polynomial-size circuit
family
is an infinite sequence of Boolean circuits
C
1
,
C
2
,...
and
such that for every
n
, the
circuit
C
n
has
n
input nodes and size
p
(
n
), where
p
(
·
) is a polynomial (fixed for the
entire family).
