Complexity Class - BPP

Let us call a nondeterministic Turing machine M balanced if for every input x, all of its computational paths have the same length, i.e., the number of nondeterministic bits depends only on x and not on previous guesses. We can define the characterize class BPP as follows:

L is in BPP if there is a balanced nondeterministic polynomial-time M such that

1. If x is in L then there are at least twice as many accepting as rejecting paths of M(x).
2. If x is not in L then there are at least twice as many rejecting as accepting paths of M(x).

Suppose we use the same definition without the "balanced" requirement. This gives us the class BPP_path studied mostly in a 1997 paper of Han, Hemaspaandra and Thierauf.

BPP_path contains BPP by definition but it contains much more. Let us show that SAT is contained in BPP_path.

Let φ be a formula with n variables. Consider the following machine M(φ): Guess an assignment a for φ. If a is rejecting then reject. If a is accepting then guess n+1 bits, ignore them and accept.

If φ is not satisfiable then M(φ) will only have rejecting paths. If φ is satisfiable then it will have at least 2ⁿ⁺¹ accepting paths and at most 2ⁿ-1 rejecting paths fulfilling the requirements of the definition of BPP_path.

Han, Hemaspaandra and Thierauf prove many other results about BPP_path. The class contains MA and P^NP[log] (P with O(log n) queries to an NP language like SAT). BPP_path is contained in P^Σ₂[log], BPP^NP and PP.

Whether BPP_path is contained in ZPP^NP or Σ₂ remain the most interesting open questions about this class.