Pergunta

This seems like a silly question, but I couldn't find a conclusive answer for it.

As far as I know, ZPP contains algorithms which run in polynomial time and either return a known-correct answer or abort (this definition is equal to the one where they either return a correct answer or run in exponential time). It is also possible to get the failure probability of a ZPP algorithm arbitrarily low (but $>0$) by rerunning it often enough without using exponential time.

BPP contains algorithms which will always return an answer in polynomial time, but this answer may be wrong with at max a $\frac{1}{3}$ chance.

Therefore, given a solver for ZPP problems, I can create a function which either solves my problem or abort in $\frac{1}{3}$ of the cases, while running in polynomial time$^1$.

Given this function, I can solve any problem contained in BPP by running the function created above on it and return a random response if it aborts. Since this will be in less than $\frac{1}{3}$ of the cases, the probability for a wrong answer will be less than $\frac{1}{3}$ and it will always run in polynomial time.

This would imply that BPP is contained in ZPP, but it seems that it is actually the other way around. So where am I wrong?

$^1$ This might be my error, but it's described like this in our lecturer slides (which are not public). I couldn't find a direct citation for it, but Complexity Zoo states for RP: "implicitly: the class VPP that is defined is equivalent to RP by running the recognizer as many times as necessary to reach probability 1/2?", so I assume this can be applied to ZPP as well and my understanding is correct. EDIT: Also, in case this doesn't hold true, at least ZPP($\frac{1}{3}$) should be equal to BPP, which I couldn't find anywhere either.

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top