Czy

W literaturze nie znalazłem stwierdzenia dotyczącego i ; wskazówki będą mile widziane.N P R $\mathsf{MA}$$\mathsf{NP}^\mathsf{RP}$

Wierzę, że są równi:

• N P R $\mathsf{MA} \subseteq \mathsf{NP}^\mathsf{RP}$ : Maszyna zgaduje ciąg Merlina, a wyrocznia weryfikuje ciąg tak, jak Arthur.$\mathsf{NP}$$\mathsf{RP}$

• $\mathsf{NP}^\mathsf{RP} \subseteq \mathsf{MA}$ : Merlin zgaduje obliczenia akceptujące maszyny , w tym wszystkie połączenia, a także wyniki tych połączeń, do wyrocznia. Następnie Arthur sprawdza, czy obliczenia są prawidłowe i czy wszystkie odgadnięte wyniki wywołań wyroczni były prawidłowe. Używa amplifikacji i granic związków, aby ograniczyć całkowite prawdopodobieństwo błędu.R P R $\mathsf{NP}$$\mathsf{RP}$$\mathsf{RP}$

Czy to jest poprawne?

W pierwszej kuli potrzebowalibyśmy wyroczni, aby odpowiedzieć

• TAK, jeśli sprawdzenie Artura powiedzie się z prawdopodobieństwem (zakładając, że protokół MA ma doskonałą kompletność),$1$

• NIE, jeśli powiedzie się sprawdzenie Artura z prawdopodobieństwem .$\le 1/2$

Brzmi to jak algorytm coRP, ale haczyk polega na tym, że nie ma gwarancji, że jeden z tych dwóch warunków ma zastosowanie do każdego możliwego wkładu do wyroczni. Tak więc, Oracle nie obliczyć Corp język , ale Corp problemu obietnica i cały argumentu pokazuje tylko, że .$\mathrm{MA}\subseteq\mathrm{NP}^{\mathrm{promiseRP}}$