Introduction

Complexity Classes

Results

End

Complexity and Cryptography
Thomas Zeugmann
Hokkaido University
Laboratory for Algorithmics
https://www-alg.ist.hokudai.ac.jp/∼thomas/COCRB/

Lecture 10: Probabilistic Complexity Classes

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Probabilistic Turing Machines I
After having studied deterministic and nondeterministic
complexity classes, we finish our study of complexity by taking
a closer look at probabilistic complexity classes.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Probabilistic Turing Machines I
After having studied deterministic and nondeterministic
complexity classes, we finish our study of complexity by taking
a closer look at probabilistic complexity classes.
First, we have to define probabilistic Turing machines. This isdone informally.
Probabilistic Turing machines (abbr. PTM) are defined asdeterministic Turing machines except that they have anadditional tape equipped with a one-way read-only head. On
this auxiliary tape, an infinite sequence of zeros and ones iswritten. These zeros and ones are realizations of a sequence ofcoin flips. It is assumed that zero and one each have probability
1/2. Moreover, the coin flips are independent of one another.
Furthermore, it assumed that each realization; i.e., each infinite
sequence of zeros and ones written on the auxiliary tape isindependent of all other such sequences.
Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Probabilistic Turing Machines II

On input a string w, the PTM works as a deterministic Turingmachine. In each step of its computation it may read one
symbol from the auxiliary tape. If it does, the one-way
read-only head of the auxiliary tape moves one position to theright. Consequently, a PTM may obtain different results on thesame input, but the result is determined for every random
sequence written on the auxiliary tape.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Probabilistic Turing Machines II

On input a string w, the PTM works as a deterministic Turingmachine. In each step of its computation it may read one
symbol from the auxiliary tape. If it does, the one-way
read-only head of the auxiliary tape moves one position to theright. Consequently, a PTM may obtain different results on thesame input, but the result is determined for every random
sequence written on the auxiliary tape.
So, it remains to redefine the notion of acceptance. We present
here the usual definition found in the literature.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Probabilistic Turing Machines III

Definition 1
Let p be a constant such that 1/2 < p 6 1, let P be a PTM and let
w ∈ Σ∗ . The PTM P is said to accept w provided the probabilityof the following event E is greater than or equal to p:
Event E. P stops in an accepting configuration.
Moreover, we write Lp (P) to denote the set of all strings w ∈ Σ∗that are accepted by P with probability greater than or equal
to p.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Probabilistic Turing Machines IV
The space and time complexity of a PTM P are defined byrequesting P to obey a space or time bound f(n) in the event E
defined above. That is, on all accepting computations P uses atmost f(n) cells on all its work tapes (for space complexity)
and/or works at most f(n) steps (for time complexity).

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Probabilistic Turing Machines IV
The space and time complexity of a PTM P are defined byrequesting P to obey a space or time bound f(n) in the event E
defined above. That is, on all accepting computations P uses atmost f(n) cells on all its work tapes (for space complexity)
and/or works at most f(n) steps (for time complexity).
We are not going to provide a formal proof for the correctnessof our definition, since this is beyond the scope of this course.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Probabilistic Turing Machines IV
The space and time complexity of a PTM P are defined byrequesting P to obey a space or time bound f(n) in the event E
defined above. That is, on all accepting computations P uses atmost f(n) cells on all its work tapes (for space complexity)
and/or works at most f(n) steps (for time complexity).
We are not going to provide a formal proof for the correctnessof our definition, since this is beyond the scope of this course.
Before discussing further issues of PTMs, we exemplify theirpower by looking again at the language
L = {0n 1n | n ∈ N}.
The following theorem was found by Rūsiņš Freivalds:

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Probabilistic Turing Machines V
Theorem 1 (Freivalds (1981))
For every p with 1/2 < p < 1 there exists a constant κ > 0 and a
PTM P accepting L with probability p which uses only κ many cellson all its work tapes.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Probabilistic Turing Machines V
Theorem 1 (Freivalds (1981))
For every p with 1/2 < p < 1 there exists a constant κ > 0 and a
PTM P accepting L with probability p which uses only κ many cellson all its work tapes.
Proof. Let p with 1/2 < p < 1 be given. First, we choose two
numbers c, d ∈ N; c, d > 1, depending on p such that
 d
1
1−2·
> p and2
 c d
2
> 1−p
c
2 +1

(1)
(2)

are satisfied.
Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Probabilistic Turing Machines VI
We define the desired PTM P (again depending on p). On inputw ∈ {0, 1}∗ the PTM P does the following:(1) The PTM P checks whether or not the input w has the form
0m 1n for some m, n ∈ N. If this is not the case, P rejects w.
Otherwise, P continues by executing (2).
(2) The PTM P checks whether or not (m − n) mod c = 0. If
this is not the case, P rejects w.
Otherwise, P continues by executing (3) (see below).

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Probabilistic Turing Machines VI
We define the desired PTM P (again depending on p). On inputw ∈ {0, 1}∗ the PTM P does the following:(1) The PTM P checks whether or not the input w has the form
0m 1n for some m, n ∈ N. If this is not the case, P rejects w.
Otherwise, P continues by executing (2).
(2) The PTM P checks whether or not (m − n) mod c = 0. If
this is not the case, P rejects w.
Otherwise, P continues by executing (3) (see below).
Note that P, while executing (1) and (2), does not read any
symbol on its auxiliary tape. Clearly, (1) can be performed
without using any cells on the work tapes. It suffices to scan the
input ones, and then to return the head of the input tape to thefirst position of the input.
Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Probabilistic Turing Machines VII

For executing (2), P does not use any cell of its work tapes.
It suffices to count the number of zeros modulo c (by using
appropriate states), and then the number of ones, where P
memorizes the outcome of counting the zeros modulo c in an
appropriate state sr . Here r stands for the remainder, i.e., form mod c. From sr , the PTM P can switch to c different states(all memorizing sr ). If n mod c = r, then P switches to theparticular state in which it can start executing (3).
Otherwise, the input is already rejected, and P stops.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Probabilistic Turing Machines VII

For executing (2), P does not use any cell of its work tapes.
It suffices to count the number of zeros modulo c (by using
appropriate states), and then the number of ones, where P
memorizes the outcome of counting the zeros modulo c in an
appropriate state sr . Here r stands for the remainder, i.e., form mod c. From sr , the PTM P can switch to c different states(all memorizing sr ). If n mod c = r, then P switches to theparticular state in which it can start executing (3).
Otherwise, the input is already rejected, and P stops.
Now, P has to figure out whether or not m = n. This is done by
performing the following probabilistic experiment:

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Probabilistic Turing Machines VIII
(3) P starts on the leftmost symbol of the input and reads thewhole input from left to right, thereby also reading in eachstep a symbol from its auxiliary tape. This is done until thelast input symbol has been read. We refer to this procedure
as to a run of the experiment.
We refer to the string 0m as the left block and to 1n as theright block of the input.
A run of the experiment is successful for the left block if P
reads only zeros on its auxiliary tape while reading thezeros on its input tape.
A run of the experiment is successful for the right block if P
reads only ones on its auxiliary tape while reading the ones
on its input tape.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Probabilistic Turing Machines IX(3) A set of the experiment consists of successive runs. A set isfinished if either the run for the left block of the input was
successful or the run for the right block of the input was
successful. The set is then said to be won for the respective
block.
The experiment consists of d sets.
The PTM P accepts the input w iff each block could win atleast one set.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Probabilistic Turing Machines X

When starting (3), there are only two cases left, i.e., m = n or
|m − n| > c. It is clear that for the execution of the experiment
only a constant number κ of tape cells is sufficient.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Probabilistic Turing Machines X

When starting (3), there are only two cases left, i.e., m = n or
|m − n| > c. It is clear that for the execution of the experiment
only a constant number κ of tape cells is sufficient.
Also, it is clear that the probability to arrive at a run successful
for either the left of right block, say ε, satisfies ε > 0. Hence,
1 − ε < 1 is the probability that a run was neither successful forthe left block nor for the right block or it was successful for both
blocks. Since limn→∞ (1 − ε)n = 0, we directly see that theprobability to finish a set tends to 1 if the number of steps
performed by P tends to infinity.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Probabilistic Turing Machines XIConsequently, it remains to calculate the probability ofacceptance for the input for both cases.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Probabilistic Turing Machines XIConsequently, it remains to calculate the probability ofacceptance for the input for both cases.
Case 1. n = m.
In this case, the probability to win is for each block the same,i.e., 1/2. Therefore, the probability for the left block to win all dsets is (1/2)d and so is the probability for the right block to win
all d sets. Thus, the probability that one of the blocks wins all dsets is 2 · (1/2)d . By Inequality (1) we can conclude
 d
1
1−2·
>p,
2
and thus, with probability greater than or equal to p the input isaccepted.
Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Probabilistic Turing Machines XII
Case 2. |m − n| > c.
Without loss of generality, m < n, and thus, m + c 6 n.
Now, the conditional probability for the left block to win is=

2−m (1 − 2−n )
2−m>
2−m (1 − 2−n ) + 2−n (1 − 2−m )2−n + 2−m
2c
2c
> c
.
c
−n+m+c2 +2
2 +1Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Probabilistic Turing Machines XII
Case 2. |m − n| > c.
Without loss of generality, m < n, and thus, m + c 6 n.
Now, the conditional probability for the left block to win is=

2−m (1 − 2−n )
2−m>
2−m (1 − 2−n ) + 2−n (1 − 2−m )2−n + 2−m
2c
2c
> c
.
c
−n+m+c2 +2
2 +1

Consequently, the probability for the left block to win all d sets
can be lower bounded byComplexity and Cryptography2c2c + 1d.

c Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Probabilistic Turing Machines XIII
Finally, by Inequality (2) we can conclude

2c2c + 1


1−

d
>1−p

2c
2c + 1

and, therefored< 1 − (1 − p)
= p.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Probabilistic Turing Machines XIII
Finally, by Inequality (2) we can conclude

2c2c + 1


1−

d
>1−p

2c
2c + 1

and, therefored< 1 − (1 − p)
= p.

That is, the probability to accept a string of the form 0m 1n withm < n; i.e., not belonging to L, is less than p.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Probabilistic Turing Machines XIV

So, we have just seen what amazing computational powerprobabilism can provide if the computational resources areseverely restricted. But some remarks are in order here.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Probabilistic Turing Machines XIV

So, we have just seen what amazing computational powerprobabilism can provide if the computational resources areseverely restricted. But some remarks are in order here.
The PTM presented in the proof above is very space efficient,but not time efficient. Performing the probabilistic experimentdescribed takes a huge amount of time.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Probabilistic Turing Machines XIV

So, we have just seen what amazing computational powerprobabilism can provide if the computational resources areseverely restricted. But some remarks are in order here.
The PTM presented in the proof above is very space efficient,but not time efficient. Performing the probabilistic experimentdescribed takes a huge amount of time.
In the following we are mainly interested in algorithms thathave an efficient run-time. Thus, we shall restrict ourselves toconsider PTMs obeying an (expected) polynomial bound fortheir run time. This line of research was initiated by John Gill.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

ResultsEnd

The Complexity Class PP
Definition 2 (Gill (1977))
The probabilistic polynomial (PP) class is the set of languages L
for which there is a PTM P running in polynomial-time suchthat for all strings x we have(a) x ∈ L =⇒ Pr(x is accepted) > 1/2,(b) x < L =⇒ Pr(x is rejected) > 1/2.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

ResultsEnd

The Complexity Class PP
Definition 2 (Gill (1977))
The probabilistic polynomial (PP) class is the set of languages L
for which there is a PTM P running in polynomial-time suchthat for all strings x we have(a) x ∈ L =⇒ Pr(x is accepted) > 1/2,(b) x < L =⇒ Pr(x is rejected) > 1/2.
It can be said that PP is the weakest class of problems that canbe approximately solved in the very intuitive sense of the word.
Moreover, it seems that any problem not in PP will take morethan polynomial-time to be solved. However, no proof is
known.
Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

RemarkRequiring the majority of answers to be correct is a naturalidea. But if the correct solution is given with a probability close
to 1/2 it is hard to differentiate the incorrect solution from thecorrect one.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

RemarkRequiring the majority of answers to be correct is a naturalidea. But if the correct solution is given with a probability close
to 1/2 it is hard to differentiate the incorrect solution from thecorrect one.
Moreover, as the input size grows, we may be faced with the
problem that the probability of the correct solution tends more
and more to 1/2. Thus, such a machine will be hard to
distinguish from a machine that is simply guessing without
performing any computation. This gives way to a more
restrictive definition which we present next. Now, we are goingto bound away from 1/2 the margin of the solution.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

ResultsEnd

The Complexity Class BPP
Definition 3 (Gill (1977))
The bounded probabilistic polynomial (BPP) class is the set of
languages L for which there is a PTM P running in
polynomial-time and some constant ε > 0 such that for all
strings x we have(a) x ∈ L =⇒ Pr(x is accepted) > 1/2 + ε,(b) x < L =⇒ Pr(x is rejected) > 1/2 + ε.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

ResultsEnd

The Complexity Class BPP
Definition 3 (Gill (1977))
The bounded probabilistic polynomial (BPP) class is the set of
languages L for which there is a PTM P running in
polynomial-time and some constant ε > 0 such that for all
strings x we have(a) x ∈ L =⇒ Pr(x is accepted) > 1/2 + ε,(b) x < L =⇒ Pr(x is rejected) > 1/2 + ε.
We get BPP ⊆ PP, since 1/2 + ε > 1/2 for all ε > 0. Note that
Definition 3 can be modified and still gives the same
complexity class. In particular, for any constant ε ∈ (0, 1/2) weagain arrive at BPP.
The class BPP contains all languages that can be accepted by
efficient Monte-Carlo algorithms.
Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

ResultsEnd

The Complexity Class RP

Moreover, we can further sharpen the definition of BPP byrequiring that the PTM is making only one type of error.
More precisely, we require that for all inputs x < L, the PTM for
accepting L makes no error. Furthermore, every string from L
must be accepted with probability at least 1/2. Again, we could
replace 1/2 by any constant greater than 1/2 and less than 1.
The resulting complexity class is denoted by RP. Intuitively,
RP stands for random polynomial time though this term may be a
bit misleading.
More formally, we arrive at the following definition:

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

ResultsEnd

The Complexity Class RP
Definition 4 (Gill (1977))
The one-sided error probabilistic polynomial (RP) class is the set of
languages L for which there is a PTM P running in
polynomial-time such that for all strings x we have(a) x ∈ L =⇒ Pr(x is accepted) > 1/2,(b) x < L =⇒ x is rejected.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

ResultsEnd

The Complexity Class RP
Definition 4 (Gill (1977))
The one-sided error probabilistic polynomial (RP) class is the set of
languages L for which there is a PTM P running in
polynomial-time such that for all strings x we have(a) x ∈ L =⇒ Pr(x is accepted) > 1/2,(b) x < L =⇒ x is rejected.
As a matter of fact, we already know an important problem
belonging to RP. Recalling our results obtained in Lecture 5,
we have seen that PRIM ∈ RP, where PRIM denotes the set of
all binary representations of prime numbers.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

ResultsEnd

The Complexity Class ZPP
The last probabilistic complexity class we are going to define
represents the efficient Las Vegas algorithms.
Here, no error whatsoever is allowed and the expected run timemust be uniformly bounded by a polynomial in the length of all
inputs over the underlying alphabet Σ.
This class is denoted by ZPP and it was also defined by Gill
(1977).
So, ZPP stands for “zero-error probabilistic polynomial time.”

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

ResultsEnd

The Complexity Class ZPP
The last probabilistic complexity class we are going to define
represents the efficient Las Vegas algorithms.
Here, no error whatsoever is allowed and the expected run timemust be uniformly bounded by a polynomial in the length of all
inputs over the underlying alphabet Σ.
This class is denoted by ZPP and it was also defined by Gill
(1977).
So, ZPP stands for “zero-error probabilistic polynomial time.”
Theorem 2 establishes the more obvious relations with respect
to set inclusion between the probabilistic complexity
complexity classes and some other previously definedcomplexity classes.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Results I

Let us recall the notion of a balanced TM.
Definition 5
An NTM is balanced if all computation paths over a string x areof the same length and, moreover, each state is a guess state.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Results I

Let us recall the notion of a balanced TM.
Definition 5
An NTM is balanced if all computation paths over a string x areof the same length and, moreover, each state is a guess state.
Now, it is easy to see that every NP machine M can be replaced
by a balanced NTM M 0 such that L(M) = L(M 0 ).

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Results II

Furthermore, the notion of a balanced NTM can be easily
adapted to a PTM. The only modification to be made is toreplace “guess state” by “coin-tossing” state.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Results II

Furthermore, the notion of a balanced NTM can be easily
adapted to a PTM. The only modification to be made is toreplace “guess state” by “coin-tossing” state.
Exercise 1. Prove that for every PTM P accepting a language L inthe sense of PP there is balanced PTM P 0 such that
L(P) = L(P 0 ) = L.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Results III
Theorem 2(1) P ⊆ ZPP ⊆ RP ⊆ BPP ⊆ PP ⊆ PSPACE;(2) RP ⊆ NP ⊆ PP;(3) ZPP, RP and BPP are closed under union and intersection.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Results III
Theorem 2(1) P ⊆ ZPP ⊆ RP ⊆ BPP ⊆ PP ⊆ PSPACE;(2) RP ⊆ NP ⊆ PP;(3) ZPP, RP and BPP are closed under union and intersection.
First, we prove Assertion (1). Clearly, by definition we haveP ⊆ ZPP ⊆ RP and BPP ⊆ PP (as already mentioned above).

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Results III
Theorem 2(1) P ⊆ ZPP ⊆ RP ⊆ BPP ⊆ PP ⊆ PSPACE;(2) RP ⊆ NP ⊆ PP;(3) ZPP, RP and BPP are closed under union and intersection.
First, we prove Assertion (1). Clearly, by definition we haveP ⊆ ZPP ⊆ RP and BPP ⊆ PP (as already mentioned above).
For seeing that PP ⊆ PSPACE it suffices to notice that a PTM P
can be simulated by a deterministic TM M which performs all
possible computations of P. Additionally, M counts the numberof accepting computations and makes at the end a majority
vote. We omit the details.
Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Results IV

Claim: RP ⊆ BPP
Let L be accepted in the sense of RP by a PTM P. Thus, if x < Lthen x is always rejected.
If x ∈ L, then Pr(x is accepted) > 1/2. Thus, we can construct a
PTM P 0 which behaves as follows: On every input x it runs the
PTM P exactly twice. The PTM P 0 accepts x, if x has been
accepted by P at least once. Hence, if x < L, then P 0 will neveraccept x, too. On the other hand, if x ∈ L, then P 0 makes an error
if and only if P has made an error on x twice. The probability
that P is not accepting x twice is, however, less than 1/4. Hence
P 0 accepts L in the sense of BPP. This proves Assertion (1).

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

ResultsEnd

RP ⊆ NP

Assume a language L that is accepted in the sense of RP by a
PTM P. Again, if x < L, then x is always rejected. Thus, we cansimply remove the coin-flips made by P and replace them by anondeterministic choice. Hence, the resulting machine M
nondeterministically accepts L. This proves RP ⊆ NP.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

NP ⊆ PP
Next, we have to show that NP ⊆ PP. Let L ∈ NP be witnessedby the NTM M.
First recall that for all x < L there is no accepting computationof M for x.
But if x ∈ L, then at least one accepting computation of M for x
must exist. However, the desired PTM P has to accept/reject astring x if the majority of the computations performed is
accepting/rejecting x. For reaching this goal, we proceed asfollows:

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

NP ⊆ PP
Next, we have to show that NP ⊆ PP. Let L ∈ NP be witnessedby the NTM M.
First recall that for all x < L there is no accepting computationof M for x.
But if x ∈ L, then at least one accepting computation of M for x
must exist. However, the desired PTM P has to accept/reject astring x if the majority of the computations performed is
accepting/rejecting x. For reaching this goal, we proceed asfollows:
Let M be a balanced NTM and let L(M) be the language
accepted by M. Moreover, there exists a polynomial p such that
M takes time p(|x|) on all inputs x. Without loss generality wecan also assume that Σ = {0, 1}. We construct a balanced PTM P
from the machine M as follows:
Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

NP ⊆ PPFirst, each guessing state is replaced by a coin-tossing state. The
outcome of a coin-toss then corresponds to a guess. Eachterminal node of the computation tree of M over a string x withn = |x| is then reached with probability 1/2p(n) .
Now, a further computation is carried out at each such leaf.
That is, the terminal leaves of M’s computation tree on x are nolonger terminal leaves for the computation tree of P over x.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

NP ⊆ PPLet q be a polynomial such that p(n) 6 q(n) for all n ∈ N.
If the terminal leaf of M’s computation tree on x is rejecting,then P will toss its coin q(n) times. If not all outcomes of thesecoin tosses are head, then P tosses the coin again.
It accepts if the last coin toss is head and rejects x otherwise.
If all outcomes of these q(n) coin tosses are head, then P tosses
the coin again (for being balanced) but rejects the input x
regardless of the outcome of the last coin toss.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

NP ⊆ PPLet q be a polynomial such that p(n) 6 q(n) for all n ∈ N.
If the terminal leaf of M’s computation tree on x is rejecting,then P will toss its coin q(n) times. If not all outcomes of thesecoin tosses are head, then P tosses the coin again.
It accepts if the last coin toss is head and rejects x otherwise.
If all outcomes of these q(n) coin tosses are head, then P tosses
the coin again (for being balanced) but rejects the input x
regardless of the outcome of the last coin toss.
On the other hand, if the reached terminal leaf in M’s
computation tree on x is accepting, then machine P tosses its
coin again q(n) + 1 times and accepts regardless of the outcome(again this done only to make P balanced).

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

NP ⊆ PP

Case 1. x < L(M).
Then, the definition of P directly implies that
Pr(x is rejected|x < L) ==Complexity and Cryptography
2p(n) 2q(n) + 1
2p(n)+q(n)+1
1
1+ q(n)+1 .
2 2

c Thomas Zeugmann

Introduction

Complexity Classes

Results

End

NP ⊆ PP
Case 2. x ∈ L(M).

Pr(x is acc.| x ∈ L) >

2p(n) − 1 2q(n) − 1
2q(n)+1+
2p(n)+q(n)+12p(n)+q(n)+1=

1 2q(n) − 2p(n) + 1+
22p(n)+q(n)+1>

1
2since q(n) > p(n) .

Hence P accepts L(M) in the sense of PP. This completes theproof of Assertion (2).

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

ResultsEnd

ZPP is closed under union and intersection

Consider two PTMs P and P 0 such that L(P) and L(P 0 ) are
accepted in the sense of ZPP.
Then it easy to see that a PTM P̂ accepts L(P) ∩ L(P 0 )( L(P) ∪ L(P 0 ) ) in the sense of ZPP if P̂ works as follows:
It simulates both P and P 0 and accepts its input x if P and P 0
accept x ( if P or P 0 accept x ).
We leave it as an exercise to show the closure with respect tounion and disjunction for the remaining classes mentioned inAssertion (3).

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

ResultsEnd

ZPP = RP ∩ co-RP

Next, we mention the following characterization for ZPP:
Theorem 3
ZPP = RP ∩ co-RP.
The proof is provided in the book.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Final Remarks
We like to conclude our short excursion into the field ofrandomized computations by mentioning that there is muchmore.
In particular, it is not too hard to prove that there are complete
problems for PP. The perhaps easiest PP-complete problem is
MAJ defined as the set of all Boolean formulae that are satisfied
by the majority of possible assignments of the variables
occurring in them.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Final Remarks
We like to conclude our short excursion into the field ofrandomized computations by mentioning that there is muchmore.
In particular, it is not too hard to prove that there are complete
problems for PP. The perhaps easiest PP-complete problem is
MAJ defined as the set of all Boolean formulae that are satisfied
by the majority of possible assignments of the variables
occurring in them.
Furthermore, it has been a long standing open problem
whether or not PP is also closed under union and intersection.
This problem got solved in 1991, but the proof technique used
is too complex to be included here. We refer the reader to
Beigel et al. (1991).
Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Final Remarks

But we do not know any problem that is complete for BPP
under polynomial time reductions.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Final Remarks

But we do not know any problem that is complete for BPP
under polynomial time reductions.
One reason for the difficulty to find a problem that is complete
for BPP is that the defining property of the class BPP issemantic. That is, for every string x over the underlying
alphabet, a Turing machine has either to accept x withprobability at least 1/2 + ε or it has to reject it with probability
at least 1/2 + ε. Given a description of a Turing machine, it isundecidable whether or not it has this property.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Summary
The following figure summarizes the known inclusions
between the probabilistic complexity classes and relates themto P and PSPACE, where A → B stands for A ⊆ B:
co-RP

P

ZPP

co-NP

BPP

RP

PP

PSPACENP

Figure 1: Inclusions between complexity classes.

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

Thank you!

Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

ResultsEnd

Rūsiņš Freivalds
Complexity and Cryptographyc Thomas Zeugmann

Introduction

Complexity Classes

Results

End

John Gill

Complexity and Cryptographyc Thomas Zeugmann