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 ?
źródło
Odpowiedzi:
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 ( a0, a1, ⋯ , an) dla każdego z m równańmod p .
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.
źródło