Information Technology Reference
In-Depth Information
Pairing functions can be very easy to describe and compute. For example,
<
x
,
y
>
can
be implemented by representing 0 by 01, 1 by 10, both
<
and
>
by 11, and , (comma) by 00.
Thus,
<
0010, 110
>
is encoded as 11010110010010100111. It is clearly trivial to identify,
extract, and decode each component of the pair. We are now prepared to define
P/poly
.
DEFINITION
8.15.4
Let
a
:
→B
∗
be a polynomial advice function.
P/poly
is the set of
languages
L
=
{
w
|
<
w
,
a
(
|
w
|
)
>
∈
A
}
for which there is a language
A
in
P
.
The
advice
a
(
|
w
|
)
givenonastring
w
in a language
L
∈
P/poly
isthesameforall
strings of the same length. Furthermore,
<
w
,
a
(
|
w
|
)
>
must be easy to recognize, namely,
recognizable in polynomial time.
Thesubsetofthelanguagesin
P/poly
for which the advice function is the empty string is
exactly the languages in
P
,thatis,
P
P/poly
.
The following result is the principal result of this section. It gives two different interpreta-
tions of the advice given on strings.
⊆
THEOREM
8.15.2
A language
L
is recognizable by a family of circuits of polynomial size if and
only if
L
∈
P/poly
.
Proof
Let
L
be recognizable by a family
C
of circuits of polynomial size. We show that it is
in
P/po
ly
.
Let
C
n
be an encodi
ng
of the circuit
C
n
in
n
.Letthe
C
that recognizes strings in
L
∩B
∈B
∗
have length
n
.Then,
w
n
advice function
a
(
n
)=
C
n
and let
w
∈B
if and only if
n
the value of
C
n
on
w
is 1. Since
w
has length polynomial in
n
,
w
∈B
if and only if the
pairing function
<
w
,
a
(
)
>
is an instance of
CIRCUIT SAT
, which has been shown to
be in
P
.(SeeTheorem
8.13.2
.)
On the other hand, suppose that
L
|
w
|
P/poly
. We show that
L
is recognizable by circuits
of polynomial size. By definition there is an advice function
a
:
∈
→B
∗
and a language
A
∈
P
for
L
such that for all
w
∈
L
,
<
w
,
a
(
|
w
|
)
>
∈
A
.Since
A
∈
P
,thereisa
polynomial-time DTM that accepts
<
w
,
a
(
|
w
|
)
>
.ByTheorem
8.13.1
there is a circuit
of polynomial size that recognizes
<
w
,
a
(
|
w
|
)
>
.Thestring
a
(
|
w
|
)
is constant for strings
n
to which is supplied the constant string
a
(
w
of length
n
. Thus, the circuit for
A
∩B
|
w
|
)
is a circuit of length polynomial in
n
that accepts strings
w
in
L
.
.......................................
Problems
MATHEMATICAL PRELIMINARIES
A
8.1 Show that if strings over an alphabet
with at least two letters are encoded over a
one-letter alphabet (a
unary encoding
), then strings of length
n
over
A
require strings
of length exponential in
n
in the unary encoding.
8.2 Show that the polynomial function
p
(
n
)=
K
1
n
k
can be computed in
O
(log
2
n
)
serial
steps from
n
and for constants
K
1
≥
1and
k
≥
1 on a RAM when additions require
one unit of time.
Search WWH ::
Custom Search