Czy wymaganie jednoznaczności poprawnych odpowiedzi dla Merlina ogranicza moc protokołów Arthur-Merlin?

Preambuła.

Klasa złożoności AM to te problemy, które można rozwiązać za pomocą dwóch okrągłych interaktywnych systemów dowodowych między sprawdzonym „Merlinem” a weryfikatorem „Arthurem”. Problem - który testuje niektóre właściwości obiektu X - występuje w AM, jeśli:

• W przypadku TAK , dla losowego komunikatu „wyzwanie” (o wielomianowej długości) Arthur generuje z dużym prawdopodobieństwem, że Merlin może sformułować odpowiedź (o wielomianowej długości), którą Arthur może wykorzystać jako dowód, że X ma właściwość;

• Dla NO przypadkach random wiadomości wyzwanie Arthur generuje, z dużym prawdopodobieństwem Merlin nie można sformułować żadnej odpowiedzi, które mogą być wykorzystane jako dowód własności badanego w na X .

- Opisana klasa nie zmienia się, jeśli wymagamy od Merlina udzielenia użytecznej odpowiedzi nie tylko z dużym prawdopodobieństwem, ale także w przypadku każdego wyzwania, które Arthur może wystawić; moglibyśmy powiedzieć w tym przypadku, że wymagamy, aby odpowiedź Merlina była zawsze ważna dla przypadków TAK , a tym, co testuje Arthur, jest poprawność odpowiedzi. Więc jeśli Merlin kiedykolwiek wyda nieprawidłową odpowiedź, Arthur wie, że wystąpienie problemu jest NIE wystąpieniem. To ustawienie wolę rozważyć.

Przykładem jest wykres nieizomorfizm: biorąc pod uwagę wykresy G i H z tym samym zestawem etykiet wierzchołków, Arthur może losowo wybrać jeden z wykresów i stworzyć „zakodowaną” wersję F , permutując etykiety wierzchołków, wysyłając prezentację do Merlina . Jeśli dwa wykresy nie są izomorficzne, Merlin może zidentyfikować, który z G lub H Arthur wybrał, określając, czy F  ≅  G lub F  ≅  H , i może odpowiedzieć, identyfikując, który z dwóch F jest izomorficzny. Jeśli dwa wykresy G i H są izomorficzne, Merlin nie może rozróżnić, który wykresF przyszedł i każda udzielona odpowiedź może być poprawna tylko przez przypadek. Dlatego w przypadku TAK, Merlin może zawsze wysłać prawidłową odpowiedź na każde wyzwanie; dla NO przypadkach jakiejkolwiek odpowiedzi, które może wysłać Merlin będzie z dużym prawdopodobieństwem jest nieprawidłowa.

W powyższym problemie nie tylko istnieje poprawna odpowiedź, którą Merlin może udzielić Arthurowi dla każdego wyzwania, ale w rzeczywistości istnieje unikalna ważna odpowiedź: tj.  Wskazać, który z G lub H Arthur wybrał, biorąc pod uwagę, że można to ustalić na podstawie określenie, które jest izomorficzny F .

Pytanie.

Czy nałożenie ograniczenia wzdłuż tych linii - że dla przypadków TAK , dla każdego wyzwania, które Arthur mógłby wysłać, istnieje dokładnie jedna poprawna odpowiedź dla Merlina - daje bardziej restrykcyjną klasę, w sensie uzyskania klasy, która nie jest znana jako równa AM ?

Artykuł Koirana Nullstellensatz Hilberta znajduje się w Hierarchii Wielomianowej, który udostępnia protokół Arthura-Merlina z monetami publicznymi do ustalenia, że ​​układ równań $m$ na $n$ niewiadomych ma rozwiązanie w $\mathbb{C}^n$ , zależne od uogólnionej hipotezy Riemanna. Tutaj Merlin znajduje się doskonałą $p$ o $H(p)=0$ dla niektórych losowego mieszania $H$ , wraz z roztworem $(a_0,a_1,\cdots, a_n)$ dla każdego z $m$ równań$\bmod p$ .

$\bmod p$$p$$\bmod p$$p$$p$

$p$$\mathbb{C}^n$$p$$a$$1-1/e$

Zatem w powyższym problemie nie tylko istnieje ważna odpowiedź, którą Merlin może wydać Arthurowi na każde wyzwanie, ale w rzeczywistości może istnieć duża liczba prawidłowych odpowiedzi.

$p$$p$