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

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

_{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^{n+1} accepting paths and at most 2^{n}-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^{Σ2[log]}, BPP^{NP} and
PP.

Whether BPP_{path} is contained in ZPP^{NP} or Σ_{2} remain
the most interesting open questions about this class.

Are there relativisations for the "BPPpath in ZPPNP or Σ2"? (I do not know if I will get an answer on a four-year-old post :) )

ReplyDeleteYes there is a relatized world where BPPpath is not contained in Σ2 (and thus also not contained in ZPP^NP). See this post.

ReplyDelete