Cryptography Reference
In-Depth Information
gets the same advice (i.e.,
a
n
) on all inputs of the same length (i.e.,
n
). Intuitively,
the advice
a
n
may be useful in some cases (i.e., for some computations on inputs of
length
n
), but it is unlikely to encode enough information to be useful for all 2
n
possible
inputs.
Another way of looking at non-uniform polynomial-time “machines” is to consider
an infinite sequence of Turing machines,
M
1
,
such that both the length of the
description of
M
n
and its running time on inputs of length
n
are bounded by polynomials
in
n
(fixed for the entire sequence). Machine
M
n
is used only on inputs of length
n
. Note
the correspondence between the two ways of looking at non-uniform polynomial time.
The pair (
M
M
2
,...,
)) (of the first definition) gives rise to an infinite sequence of
machines
M
a
1
,
M
a
2
,...,
where
M
a
|
x
|
(
x
)
def
,
(
a
1
,
a
2
,...
=
M
(
x
,
a
|
x
|
). On the other hand, a sequence
M
1
,
M
2
,...
(as in the second definition) gives rise to a pair (
U
,
(
M
1
,
M
2
,...
)),
where
U
is the universal Turing machine and
M
n
is the description of machine
M
n
(i.e.,
U
(
x
,
M
|
x
|
)
=
M
|
x
|
(
x
)).
In the first sentence of this Section 1.3.3, non-uniform polynomial time was referred
to as a stronger model than probabilistic polynomial time. That statement is valid in
many contexts (e.g., language recognition, as seen later in Theorem 1.3.7). In particular,
it will be valid in all contexts we discuss in this topic. So we have the following informal
“meta-theorem”:
Meta-theorem:
Whatever can be achieved by probabilistic polynomial-time
machines can be achieved by non-uniform polynomial-time “machines.”
The meta-theorem clearly is wrong if we think of the task of tossing coins. So
the meta-theorem should not be understood literally. It is merely an indication of real
theorems that can be proved in reasonable cases. Let us consider, for example, the
context of language recognition.
Definition 1.3.6:
The complexity class
non-uniform polynomial time (
denoted
P
/
poly)
is the class of languages L that can be recognized by a non-uniform
sequence of polynomial time “machines.” Namely, L
poly
if there exists an
infinite sequence of machines M
1
,
M
2
,...
satisfying the following:
∈
P
/
1.
There exists a polynomial p
(
)
such that for every n, the description of machine
M
n
has length bounded above by p
(
n
)
.
2.
There exists a polynomial q
(
·
)
such that for every n, the running time of machine
M
n
on each input of length n is bounded above by q
(
n
)
.
3.
For every n and every x
·
n
, machine M
n
will accept x if and only if x
∈{
0
,
1
}
∈
L.
Note that the non-uniformity is implicit in the absence of a requirement concerning
the construction of the machines in the sequence. It is required only that these ma-
chines exist. In contrast, if we augment Definition 1.3.6 by requiring the existence of
a polynomial-time algorithm that on input 1
n
(
n
presented in unary) outputs the de-
scription of
M
n
, then we get a cumbersome way of defining
P
. On the other hand, it
