Cryptography Reference
In-Depth Information
but is associated with a random variable, and that this random variable typically
assigns error probabilities to the event of recognizing the instance. Consequently,
one has to consider the possibility that a probabilistic polynomial-time Turing
machine may introduce errors and that the machine may recognize a problem
instance only with certain error probabilities.
Let
M
be a probabilistic polynomial-time Turing machine,
D
}
∗
a
⊆{
0
,
1
}
∗
an input for
M
. The following two probability
decision problem, and
x
∈{
0
,
1
bounds are relevant for
M
:
(
1
Pr[
M
outputs Yes
|
x
∈
D
]
≥
∈
2
,
1]
[0
,
1
Pr[
M
outputs Yes
|
x/
∈
D
]
≥
δ
∈
2
)
The first probability bound is for a correct answer and is sometimes called
completeness probability bound
. The need for bounding this probability from below
is to limit the possibility to mistakenly output a no answer:
Pr[
M
outputs No
|
x
∈
D
]
<
1
−
The second probability bound limits the probability that
M
mistakenly outputs
yes. It is called the
soundness probability bound
, and the need for bounding it from
above is quite obvious.
Note that we have expressed the probability bounds for
M
with two constants
and
δ
taken from large intervals. This imprecision, however, does not cause any
problem (if necessary, we can always run
M
multiple times to narrow down the
intervals).
The complexity class
has several subclasses which are defined by different
(completeness and soundness) probability bounds, using different values for
and
δ
, respectively.
PP
6.6.3.1
Zero-Sided Errors
If we assume that a probabilistic polynomial-time Turing machine
M
does not make
any error on either side, then we can formally introduce the complexity class
ZPP
as suggested in Definition 6.13.
Definition 6.13 (Complexity class
ZPP
)
ZPP
(“zero-sided-error probabilistic
polynomial time”) is a subclass of
PP
. It comprises all decision problems
D
⊆
