Complexity class BPP, but with only expected polynomial running time

Question

The complexity class BPP requires that the running time be guaranteed polynomial, though with only a 2/3 chance of the correct output.

ZPP, on the other hand, guarantees correct output, but now only requires that expected running time be polynomial.

Is there some complexity class with both: it only requires the running time be expected polynomial, and also only requires a 2/3 chance of success?

If so, how large is this class? Is it strictly larger than BPP, and would it be feasible? What are some problems in this class that aren't in BPP or ZPP?

Answer 1

This is the same as BPP.

Let $A$ be an algorithm whose expected running time is polynomial, say $p(n)$, and that has a probability $\ge 2/3$ of giving the corrected answer.

Let $B$ an algorithm that runs $A$ for $4p(n)$ steps, and terminates it if it runs longer than that. If it is terminated early, flip a coin and return a random answer; otherwise, returns whatever $A$ did. Notice that the probability that $B$ returns the correct answer is

$$\ge (3/4)\times (2/3) + (1/4) \times (1/2) = 5/8.$$

Let $C$ be an algorithm that runs $B$ 3 times on the same input, and takes a majority vote of its outputs. Then the probability that $C$ returns the correct answer is

$$\ge (5/8)^3 + {3 \choose 1} \cdot(5/8)^2 \cdot (3/8),$$

which is $>2/3$ if you do the arithmetic.

We conclude that $C$'s running time is guaranteed to be at most $12p(n)$, which is polynomial, and $C$ has at least a $2/3$ chance of outputting the correct answer. This proves that the problem is in BPP.

Thanks to @Mike Battaglia and Emil Jeřábek for this argument.