Perché $ zpp geq bpp $ non è vero?

Question

Questa sembra una domanda sciocca, ma non sono riuscito a trovare una risposta conclusiva per questo.

Per quanto ne so, ZPP contiene algoritmi che funzionano nel tempo polinomiale e restituiscono una risposta o abort a correzione conosciuta (questa definizione è uguale a quella in cui restituiscono una risposta corretta o eseguono in tempo esponenziale). È anche possibile ottenere la probabilità di fallimento di un algoritmo ZPP arbitrariamente basso (ma $>0$) rientrandolo abbastanza spesso senza usare il tempo esponenziale.

BPP contiene algoritmi che restituiranno sempre una risposta in tempo polinomiale, ma questa risposta potrebbe essere sbagliata con Max A $ frac {1} {3} $ opportunità.

Pertanto, dato un risolutore per i problemi di ZPP, posso creare una funzione che risolve il mio problema o abortire $ frac {1} {3} $ dei casi, mentre corri in tempo polinomiale$^1$.

Data questa funzione, posso risolvere qualsiasi problema contenuto in BPP eseguendo la funzione creata sopra su di essa e restituire una risposta casuale se interrompe. Dal momento che questo sarà in meno di $ frac {1} {3} $ dei casi, la probabilità per una risposta sbagliata sarà inferiore a $ frac {1} {3} $ E funzionerà sempre in tempo polinomiale.

Ciò implicherebbe che BPP sia contenuto in ZPP, ma sembra che sia in realtà il contrario. Allora dove sbaglio?

$^1$ Questo potrebbe essere il mio errore, ma è descritto così nelle nostre diapositive docente (che non sono pubbliche). Non sono riuscito a trovare una citazione diretta per questo, ma zoo di complessità stati per rp: "Implicitamente: il VPP di classe definito è equivalente a RP eseguendo il riconoscimento tutte le volte necessarie per raggiungere la probabilità 1/2?", Quindi presumo che questo possa essere applicato anche a ZPP e la mia comprensione è corretta. Modifica: anche nel caso in cui ciò non sia vero, almeno ZPP ($ frac {1} {3} $) dovrebbe essere uguale a BPP, che non sono riuscito a trovare da nessuna parte.