6.4  Probabilistic Polynomial Time

      Probabilistic Time Complexity
      Probabilistic Complexity Classes
      Relationships between Probabilistic and Nonprobabilistic Complexity Classes

As in the case of deterministic and nondeterministic Turing transducers, each move of a probabilistic Turing transducer is assumed to take one unit of time. The time that a computation takes is assumed to be equal to the number of moves made during the computation. The space the computation takes is assumed to equal the number of locations visited in the auxiliary work tape, which has the maximal such number.

 Probabilistic Time Complexity

A probabilistic Turing transducer M is said to be T(n) time-bounded , or of time complexity T(n), if M halts within T(n) time in each computation on each input of length n. If T(n) is a polynomial, then M is also said to be polynomially time-bounded, or to have polynomial time complexity.

M is said to be T(n) expected time-bounded, or of expected time complexity T(n), if for each input x of M the function T(n) satisfies

If T(n) is a polynomial, then M is said to be polynomially expected time-bounded, or of polynomially expected time complexity.

Arguments similar to those given for Church's Thesis in Section 4.1, and for the sequential computation thesis in Section 5.1, also apply for the following thesis.

The Probabilistic Computation Thesis     A function that is computable mechanically with the aid of probabilistic choices can also be computed by a probabilistic Turing transducer of polynomially related time complexity and polynomially related, expected time complexity.

 Probabilistic Complexity Classes

The tractability of problems with respect to probabilistic time is determined by the existence of bounded-error probabilistic Turing transducers of polynomial time complexity for solving the problems. In light of this observation, the following classes of language recognition problems are of interest here.

BPP -- the class of membership problems for the languages in

{ L | L is a language accepted by a bounded-error probabilistic Turing machine of polynomial time complexity }.

RP -- the class of membership problems for the languages in

{ L | L is a language accepted by a polynomially time-bounded, probabilistic Turing machine M, which satisfies the following two conditions for some constant < 1.

1.  On input x from L, M has an accepting computation with probability 1 - e(x) 1 - .
2.  On input x not from L, M has only nonaccepting computations. }

ZPP -- the class of membership problems for the languages in

{ L | L is a language accepted by a probabilistic Turing machine, which has zero error probability and polynomially expected time complexity. }

 Relationships between Probabilistic and Nonprobabilistic
Complexity Classes

The relationship between the different classes of problems, as well as their relationship to the classes studied in Chapter 5, is illustrated in Figure 6.4.1.

Figure 6.4.1 A hierarchy of some classes of problems.

Theorem 6.4.1    BPP is included in PSPACE.

Proof     Consider any problem K in BPP. Let L denote the language that K induces. By the definition of BPP there exists a bounded-error, polynomially time-bounded, probabilistic Turing machine M₁ that accepts L. Let < 1/2 be a constant that bounds the error probability of M₁, and let p(n) be the time complexity of M₁.

With no loss of generality it is assumed that M₁ has a constant k, such that in each probabilistic move, M₁ has exactly k options. (Any probabilistic Turing machine can be modified to have such a property, with k being the least common multiple of the number of options in the different moves of the Turing machine.) In addition, it is assumed that M₁ has some polynomial q(n), such that in each computation on each input x it makes exactly q(|x|) probabilistic moves. Consequently, M₁ on each input x has exactly k^q(|x|) possible computations, with each computation having an equal probability of occurring.

From M₁, a deterministic Turing machine M₂ can be constructed to accept the language L. M₂ relies on the following two properties of M₁.

1.  If x is in L, then M₁ has at least probability 1- > 1/2 of having an accepting computation on input x.
2.  If x is not in L, then M₁ has at least probability 1 - > 1/2 of having a nonaccepting computation on input x.

Given an input x, the Turing machine M₂ starts its computation by computing p(|x|). Then one at a time, M₂ lists all the sequences of transition rules of M₁ whose lengths are at most p(|x|). For each such sequence, M₂ checks whether the sequence corresponds to a computation of M₁. M₂ determines whether each computation of M₁ is accepting or rejecting. In addition, M₂ counts the number m_a of accepting computations, and the number m_r of nonaccepting computations.

M₂ accepts the input x if it determines that the probability m_a/(m_a + m_r) of M₁ accepting x is greater than 1/2, that is, if m_a > m_r. M₂ rejects x if it determines that the probability m_r/(m_a + m_r) of M₁ rejecting x is greater than 1/2, that is, if m_r > m_a.

The nonprimality problem is an example of a problem in the class RP (see Example 6.2.1). For RP the following result holds.

Theorem 6.4.2    RP is in BPP NP.

Proof     Consider any problem K in RP. Let L be the language that K induces. By the definition of RP, it follows that there exist a constant < 1, and a polynomially time-bounded Turing machine M₁, that satisfy the following conditions.

1.  If x is in L, then M₁ has a probability 1 - > 0 of having an accepting computation on x.
2.  If x is not in L, then M₁ has only nonaccepting computations on x.

M₁ can also be simulated by a bounded-error probabilistic Turing machine M₃ of similar time complexity. Specifically, let k be any constant such that ^k < 1/2. Then M₃ simulates k computations of M₁ on a given input x. M₃ accepts x if M₁ accepts x in any of the simulated computations. Otherwise, M₃ rejects x. It follows that RP is also in BPP.

Finally, for ZPP the following result is shown.

Theorem 6.4.3    ZPP is contained in RP.

Proof     Consider any probabilistic Turing machine M₁ that has 0 error probability. Let (n) denote the expected time complexity of M₁. Assume that (n) is some polynomial in n.

From M₁, a probabilistic Turing machine M₂ of the following form can be constructed. Given an input x, the probabilistic Turing machine M₂ starts its computation by evaluating (|x|). Then M₂ simulates c(|x|) moves of M₁ on input x for some constant c > 1. M₂ halts in an accepting state if during the simulation it reaches an accepting state of M₁. Otherwise, M₂ halts in a nonaccepting state.

By construction M₂ has no accepting computation on input x if x is not in L(M₁). On the other hand, if x is in L(M₁), then M₂ halts in a nonaccepting state, with probability equal to that of M₁ having an accepting computation that requires more than c(|x|) moves. That is, the error probability e(x) is equal to _i=c(|x|)+1p_i, where p_i denotes the probability that, on x, M₁ will have a computation that takes exactly i steps.

Now

(|x|)		(x)
	=	p0 0 + p1 1 + + pc(|x|) c(|x|) +
		p0 0 + p1 1 + + pc(|x|) c(|x|) + i=c(|x|)+1p i
	=	p0 0 + p1 1 + + pc(|x|) c(|x|) + (c(|x|) + 1)e(x)
	=	e(x) +

1 - e(x)		1 -
		1 - 1/c

[next] [prev] [prev-tail] [front] [up]