Previous CCW 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 Σ_{2}remains the most interesting open question about this class.

--

Posted by Lance Fortnow to My Computational Complexity Web Log at 2/17/2003 11:05:32 AM

Powered by Blogger Pro