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

15

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 ?

Niel de Beaudrap
źródło
Zanim zastanowię się, czy jest równy AM czy nie, nawet nie widzę, jak udowodnić, że NP jest zawarty w twojej klasie…
Tsuyoshi Ito
1
Jeśli wymagamy od Merlina jednej prawidłowej odpowiedzi tylko z dużym prawdopodobieństwem, wówczas klasa zawiera NP (i, jak sądzę, całą AM): możemy zmusić Arthura do przeprowadzenia redukcji Valiant – Vazirani do Unique-SAT.
Emil Jeřábek wspiera Monikę
@Emil: Rozumiem, że jeśli „wysokie prawdopodobieństwo” wynosi 1 / poli, ale czy można zwiększyć to prawdopodobieństwo, powiedzmy, na stałe?
Tsuyoshi Ito
W porządku, to raczej niewielkie prawdopodobieństwo. Nie wiem, jak to zrobić.
Emil Jeřábek wspiera Monikę
1
Czy rozważasz protokoły monet publicznych lub protokoły monet prywatnych? Z definicji wydaje się, że myślisz o protokołach monet publicznych, ale opisany przez ciebie protokół nieizomorfizmu grafów nie jest protokołem monet publicznych.
Tsuyoshi Ito

Odpowiedzi:

1

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 don , 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 (za0,za1,,zan) dla każdego z m równańmodp .

modppmodppp

pdonpza11/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.

pp

Znaki
źródło