Cryptography Reference
In-Depth Information
BPP
is the class of languages that can be recognized by a probabilistic polynomial-
time Turing machine (i.e., randomized algorithm).
The phrase “bounded-probability” indicates that the success probability is bounded
away from
1
2
3
2 . In fact, in Definition 1.3.4, replacing the constant
by any other constant
1
2
greater than
will not change the class defined; see Exercise 4. Likewise, the constant
3 can be replaced by 1 2 −| x | and the class will remain invariant; see Exercise 5.
We conclude that languages in
2
BPP
can be recognized by probabilistic polynomial-
time algorithms with a negligible error probability. We use negligible to describe any
function that decreases faster than the reciprocal of any polynomial:
Negligible Functions
Definition 1.3.5 (Negligible): We call a function µ : N → R negligible if for
every positive polynomial p ( · ) there exists an N such that for all n > N,
1
p ( n )
µ
<
( n )
For example, the functions 2 n and n log 2 n are negligible (as functions in n ). Neg-
ligible functions stay that way when multiplied by any fixed polynomial. Namely, for
every negligible function µ and any polynomial p , the function µ ( n ) def
= p ( n ) · µ ( n )
is negligible. It follows that an event that occurs with negligible probability would
be highly unlikely to occur even if we repeated the experiment polynomially many
times.
Convention. In Definition 1.3.5 we used the phrase “there exists an N such that for
all n > N .” In the future we shall use the shorter and less tedious phrase “for all
sufficiently large n .” This makes one quantifier (i.e., the N ) implicit, and that is
particularly beneficial in statements that contain several (more essential) quantifiers.
1.3.3. Non-Uniform Polynomial Time
A stronger (and actually unrealistic) model of efficient computation is that of non-
uniform polynomial time. This model will be used only in the negative way, namely,
for saying that even such machines cannot do something (specifically, even if the
adversary employs such a machine, it cannot cause harm).
A non-uniform polynomial-time “m a chine” is a pair ( M , a ), where M is a two-input
polynomial-time Turing machine and a = a 1 , a 2 ,... is an infinite sequence of strings
such that | a n |= poly( n ). 6 For every x , we consider the computation of machine M
on the input pair ( x , a | x | ). Intuitively, a n can be thought of as extra “advice” supplied
from the “outside” (together with the input x ∈{ 0 , 1 }
n ). We stress that machine M
6 Recall that poly() stands for some (unspecified) fixed polynomial; that is, we say that there exists some
polynomial p such that | a n |= p ( n ) for all n ∈ N .
Search WWH ::




Custom Search