A probabilistic Turing machine M is a type of nondeterministic Turing
machine in which each nondeterministic step is called a coin-flip step and has
two legal next moves. We assign a probability to each branch b of M’s
computation on input w as follows. Define the probability of branch b to
be
where k is the number of coin-flip steps that occur on branch b. Define the
probability that M accepts w to be
DefinitionofPP
A language L is in PP if and only if there exists a probabilistic Turing machine
M, such that
M
runs
for
polynomial
time
on
all
inputs
For
all
x
in
L,
M
outputs
1
with
probability
strictly
greater
than
1∕2
For
all
x
not
in
L,
M
outputs
1
with
probability
less
than
or
equal
to
1∕2.
ComplexityClasses
Probabilistic Polynomial time (PP)
Definition
PP
is
the
class
of
decision
problems
solvable
by
a
probabilistic
Turing
machine
in
polynomial
time,
with
an
error
probability
of
less
than
1/2
for
all
instances.
Bounded-error Probabilistic Polynomial time (BPP)
Definition
BPP
is
the
class
of
decision
problems
solvable
by
a
probabilistic
Turing
machine
in
polynomial
time,
with
an
error
probability
of
less
than
1/3
for
all
instances.
ComplexityClassesRelationship
Theorem1
Theorem
⊆⊆ PSPACE
Proof.
The
first
inclusion
follows
from
definition.
It
is
left
for
the
reader
to
show
the
second
inclusion
by
considering
a
PPT
Turing
machine
M
that
can
solve
a
reduced
problem
(which
one?).
Thus,
PP ⊆ PSPACE. __
Hint: MAJSAT
Theorem1
Theorem
⊆⊆ PSPACE
Proof.
The
first
inclusion
follows
from
definition.
It
is
left
for
the
reader
to
show
the
second
inclusion
by
considering
a
PPT
Turing
machine
M
that
can
solve
a
reduced
problem
(which
one?).
Thus,
PP ⊆ PSPACE. __
Hint: MAJSAT
Theorem2
Theorem
⊆
Definition
From
Sipser,
a
witness
is
a
number
that
is
used
in
our
algorithm
to
accept
or
reject
a
proposed
solution.
In
other
words,
it
acts
like
a
check
in
our
process.
Theorem2
Theorem
⊆
Proof.
Let L ∈ with witnesses of size p(|x|). We give a algorithm for L on
input x:
accept
with
probability
-
otherwise,
choose
a
string
w ∈{0,1}p(|x|)
at
random
accept
iff
w
is
a
witness
for
input
x
(to be cont.)
Theorem2
Theorem
⊆
Proof.
(cont.)
Thus,
if
xL,
then
the
probability
that
the
above
algorithm
accepts
is
less
than
.
If
x ∈ L,
then
there
exists
at
least
one
witness
such
that
the
probability
of
acceptance
is
__
Theorem3:Preliminaries
First,
Definition
Σ0P = Π0P = P
Σk+1P := ∃PΣkP
Πk+1P := ∀PΠkP
where
∃PL := {x ∈{0,1}*∣∃w ∈{0,1}≤p(|x|) such that < x,w >∈ L} ∀PL := {x ∈{0,1}*∣∀w ∈{0,1}≤p(|x|) such that < x,w >∈ L}
Notice that Σ1P = NP, and Π1P = co - NP.
Theorem3:Preliminaries
There exists a natural hierarchy in PSPACE.
Definition
The
polynomialtimehierarchy
is
a
collection
of
classes
defined
by
Theorem3:Preliminaries
There exists a natural hierarchy in PSPACE.
Definition
The
polynomialtimehierarchy
is
a
collection
of
classes
defined
by
Thus, for every problem in there exists a deterministic, polynomial time
reduction to a counting problem.
Example1:BooleanSatisfiability(SAT)
Given a boolean formula F(x1,x2,…,xn), can F evaluate to 1 (true)?
Example
(x1∧ x2) ∨�x3
is
a
boolean
formula.
(1,1,0)
is
a
solution.
the
first
proven
-complete
problem
from
theorem
2,
in
.
Exercise:
find
a
sufficient
algorithm
to
solve
this
problem?
Example1:BooleanSatisfiability(SAT)
Given a boolean formula F(x1,x2,…,xn), can F evaluate to 1 (true)?
Example
(x1∧ x2) ∨�x3
is
a
boolean
formula.
(1,1,0)
is
a
solution.
the
first
proven
-complete
problem
from
theorem
2,
in
.
Exercise:
find
a
sufficient
algorithm
to
solve
this
problem?
Example1:BooleanSatisfiability(SAT)
Given a boolean formula F(x1,x2,…,xn), can F evaluate to 1 (true)?
Example
(x1∧ x2) ∨�x3
is
a
boolean
formula.
(1,1,0)
is
a
solution.
the
first
proven
-complete
problem
from
theorem
2,
in
.
Exercise:
find
a
sufficient
algorithm
to
solve
this
problem?
Example2MAJSAT is a special case of SAT in which you are given a boolean formula F.
The result of the formula must be 1 if more than half of all assignments
x1,x2,…,xn make F evaluate to 1 and 0 otherwise.
Theorem
MAJSATis-complete.
Proof uses many-to-one Turing reduction.
Example2MAJSAT is a special case of SAT in which you are given a boolean formula F.
The result of the formula must be 1 if more than half of all assignments
x1,x2,…,xn make F evaluate to 1 and 0 otherwise.
Theorem
MAJSATis-complete.
Proof uses many-to-one Turing reduction.
References
L.
Fortnow,
and
S.
Homer.
“A
Short
History
of
Computational
Complexity
-
Computer
Science,”
ComputationalComplexityConference(CCC),
2003.
Available:
https://people.cs.uchicago.edu/ fortnow/beatcs/column80.pdf.
J.
Katz,
”Notes
on
Complexity
Theory
Handout
7,”
TheUniversityofMaryland,
2005.
Available:
https://www.cs.umd.edu/ jkatz/complexity/f05/lecture7.pdf
E.
Allender,
M.
Loui,
K.
Regan,
”Other
Complexity
Classes
and
Measures,”
CRCHandbookonAlgorithmsandTheoryofComputations,
Ch.
29,
January
2007.
Available:
https://cse.buffalo.edu/ regan/papers/pdf/ALRch29.pdf
S.
Toda,
”PP
is
as
Hard
as
the
Polynomial-Time
Hierarchy,”
SiamJournalonComputing,
Vol.
20,
No.
5,
October
1991.
Available:
https://epubs.siam.org/doi/pdf/10.1137/0220053
![Pr [b] = 2-k](presentation0x.png)
![∑
Pr[M accepts w] = Pr[b ].
b is an accepting branch](presentation1x.png)
.
If
