Cryptography Reference
In-Depth Information
}
∗
for which there exists a probabilistic polynomial-time Turing machine
M
such that for every input
x
{
0
,
1
}
∗
∈{
0
,
1
Pr[
M
outputs Yes
|
x
∈
D
]=1
and
Pr[
M
outputs Yes
|
x/
∈
D
]=0
.
This error-probability characterization means that the probabilistic polynomial-
time Turing machine
M
does not make any error at all. This seems to imply that
ZPP
. Interestingly, this is not the case, and there are problems that
can be solved with probabilistic Turing machines more efficiently than with deter-
ministic Turing machines (both work in polynomial time).
In some literature,
is equal to
P
is defined as a subclass of decision problems which
can be solved by a probabilistic polynomial-time Turing machine in an “always fast
and always correct” fashion.
ZPP
6.6.3.2
One-Sided Errors
There are basically two possibilities for a probabilistic polynomial-time Turing
machine
M
to err on one side. The corresponding complexity classes
PP
-Monte
Carlo and
PP
-Las Vegas are introduced in Definitions 6.14 and 6.15.
Definition 6.14 (Complexity class
PP
-Monte Carlo)
PP
-Monte Carlo is a sub-
}
∗
for which a
probabilistic polynomial-time Turing machine
M
exists such that for every input
x
class of
PP
that comprises all decision problems
D
⊆{
0
,
1
∈{
0
,
1
}
∗
Pr[
M
outputs Yes
|
x
∈
D
]=1
and
Pr[
M
outputs Yes
|
x/
∈
D
]
≤
δ
(0
,
2
)
.
10
with
δ
∈
Note that in this case
δ
must be different from 0. Otherwise, the subclass
PP
-Monte Carlo
degenerates to the special case
10
ZPP
.
