Cryptography Reference
In-Depth Information
is merely the fraction of r
∈{
0
,
1
}
t M ( x ) for which M r ( x )
=
y . Namely,
r
y
∈{
0
,
1
}
t M ( x )
: M r ( x )
=
Pr
[ M ( x ) = y ] =
2 t M ( x )
The second way of looking at randomized algorithms is to view the outcome of
the internal coin tosses of the machine as an auxiliary input. Namely, we consider
deterministic machines with two inputs. The first input plays the role of the “real
input” (i.e., x ) of the first approach, while the second input plays the role of a possible
outcome for a sequence of internal coin tosses. Thus, the notation M ( x , r ) corresponds
to the notation M r ( x ) used earlier. In the second approach, we consider the probability
distribution of M ( x , r ) for any fixed x and a uniformly chosen r ∈{ 0 , 1 }
t M ( x ) . Pictorially,
here the coin tosses are not “internal” but rather are supplied to the machine by an
“external” coin-tossing device.
Before continuing, let it be noted that we should not confuse the fictitious model of
“non-deterministic” machines with the model of probabilistic machines. The former is
an unrealistic model that is useful for talking about search problems whose solutions
can be efficiently verified (e.g., the definition of
NP
), whereas the latter is a realistic
model of computation.
Throughout this entire topic, unless otherwise stated, a probabilistic polynomial-
time Turing machine means a probabilistic machine that always (i.e., independently of
the outcome of its internal coin tosses) halts after a polynomial (in the length of the
input) number of steps. It follows that the number of coin tosses for a probabilistic
polynomial-time machine M is bounded by a polynomial, denoted T M , in its input
length. Finally, without loss of generality, we assume that on input x the machine
always makes T M (
|
x
|
) coin tosses.
1.3.2.3. Associating “Efficient” Computations with
BPP
The basic thesis underlying our discussion is the association of “efficient” computations
with probabilistic polynomial-time computations. That is, we shall consider as efficient
only randomized algorithms (i.e., probabilistic Turing machines) for which the running
time is bounded by a polynomial in the length of the input.
Thesis: Efficient computations correspond to computations that can be carried
out by probabilistic polynomial-time Turing machines.
,of
languages recognizable (with high probability) by probabilistic polynomial-time Turing
machines. The probability refers to the event in which the machine makes the correct
verdict on string x .
A complexity class capturing these computations is the class, denoted
BPP
BPP
Definition 1.3.4 (Bounded-Probability Polynomial Time,
): We say that
Lis recognized by the probabilistic polynomial-time Turing machine Mif
2
for every x
L it holds that
Pr
[ M ( x )
=
1]
3 , and
2
for every x
L it holds that
Pr
[ M ( x )
=
0]
3 .
Search WWH ::




Custom Search