Czy

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

Wierzę, że są równi:

$\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. $\mathsf{NP}$ $\mathsf{RP}$ $\mathsf{RP}$

Czy to jest poprawne?

cc.complexity-theory oracles

— Joel
źródło

To zależy od tego, jak zdefiniujesz te notacje, ale jeśli zdefiniujesz te klasy złożoności jako klasy języków, twoje rozumowanie w pierwszym punkcie będzie błędne. Zobacz ∃BPP w zoo złożoności i odnośniki w nim ( Fenner, Fortnow, Kurtz i Li 2003 ).

— Tsuyoshi Ito,

Łał! Dzięki bardzo Tsuyoshi, to jest bardzo subtelna kwestia i rzeczywiście mój pierwszy punkt kuli jest błędny.

— Joel

@TsuyoshiIto: Czy to odpowiedź?

— Joshua Grochow

@Joshua: Często zamieszczam częściową odpowiedź jako komentarz, gdy z jakiegoś powodu nie chciałbym jej opublikować jako mojej odpowiedzi. Każdy powinien ponownie opublikować mój komentarz jako odpowiedź, jeśli zechce. Nie czuję się zobowiązany do opublikowania czegoś jako odpowiedzi tylko dlatego, że opublikowałem to jako komentarz.

— Tsuyoshi Ito,

@TsuyoshiIto: Dobra, rozwinąłem go w odpowiedź na cw.

— Emil Jeřábek

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}}$

— Emil Jeřábek
źródło

Nie trzeba było przekształcać tej odpowiedzi w wiki społeczności, chociaż wybór należał do ciebie.

— Tsuyoshi Ito,