Cryptography Reference
In-Depth Information
Probabilistic polynomial-time Turing machines with this error-probability
characterization have a one-sided error in the soundness side.
PP
PP
Definition 6.15 (Complexity class
-Las Vegas)
-Las Vegas is a subclass of
PP
}
∗
for which a probabilistic
polynomial-time Turing machine
M
exists such that for every input
x
that comprises all decision problems
D
⊆{
0
,
1
}
∗
∈{
0
,
1
Pr[
M
outputs Yes
|
x
∈
D
]
≥
and
Pr[
M
outputs Yes
|
x/
∈
D
]=0
(
2
,
1)
(or
with
∈
∈
(0
,
1)
, respectively).
Probabilistic polynomial-time Turing machines with this error-probability
characterization have a one-sided error in the completeness side. In either case, the
complexity classes
PP
-Monte Carlo and
PP
-Las Vegas are complementary in the
sense that
ZPP
=
PP
-Monte Carlo
∩PP
-Las Vegas.
6.6.3.3
Two-Sided Errors
If we assume that a probabilistic polynomial-time Turing machine
M
may err on
either side, then we can formally introduce the complexity class
BPP
as suggested
in Definition 6.16.
Definition 6.16 (Complexity class
BPP
)
BPP
(“bounded-error probabilistic poly-
nomial time”) is a subclass of
PP
that comprises all decision problems
D
⊆
}
∗
for which a probabilistic polynomial-time Turing machine
M
exists such
that for every input
x
{
0
,
1
}
∗
∈{
0
,
1
Pr[
M
outputs Yes
|
x
∈
D
]
≥
and
Pr[
M
outputs Yes
|
x/
∈
D
]
≤
δ
(
2
,
1)
and
δ
(0
,
2
)
.
with
∈
∈
