Pytania otagowane jako interactive-proofs

1
Referencyjne gry z niepowiązanymi półprywatnymi monetami
Byłem (i nadal jestem) bardzo zainteresowany odpowiedzią na to pytanie, ponieważ jest to interesująca odmiana złożoności gier, która nie została jeszcze rozwiązana, więc zaoferowałem nagrodę. Pomyślałem, że pierwotne pytanie jest prawdopodobnie zbyt trudne, więc zamieściłem trzy powiązane pytania, które również byłyby warte nagrody. Nikt nie opublikował żadnych odpowiedzi przed wygaśnięciem …
1
Jaki jest „prawdziwy” powód, dla którego IP = PSPACE nie powoduje relatywizacji?
OOOcoNPO⊈IPOcoNPO⊈IPO{\sf coNP}^O \not\subseteq {\sf IP}^OcoNPO⊆PSPACEOcoNPO⊆PSPACEO{\sf coNP}^O \subseteq {\sf PSPACE}^OOOO Jednak widziałem tylko kilka osób, które wyjaśniają „bezpośrednio”, dlaczego wynik nie jest relatywizowany, a typową odpowiedzią jest „arytmetyzacja”. Po sprawdzeniu dowodu IP = PSPACE ta odpowiedź nie jest fałszywa , ale nie jest dla mnie zadowalająca. Wydaje się, że „prawdziwy” powód …
2
MIP z wydajnymi dowodami
Powszechnie wiadomo, że zestawem języków posiadających dwuczłonowy interaktywny system proof, w którym weryfikator działa w czasie wielomianowym (MIP), jest NEXP. Ale czy znane są granice mocy takich interaktywnych dowodów, gdy dowody mają ograniczoną moc? Na przykład, jaka jest klasa języków, które dopuszczają dowody interaktywne z dwoma dowodami z dowodami czasu …
3
pod względem
Probabilistyczny system zapobiegania jest powszechnie określany jako ograniczenie M A , gdy Arthur można wykorzystać tylko f ( n ) losowe fragmenty i może jedynie zbadanie g ( n ) bitów certyfikat potwierdzający przesłany przez Merlin (patrz: http://en.wikipedia.org/wiki/Interactive_proof_system#PCP ).P.doP.[ f( n ) , g( n ) ]P.doP.[fa(n),sol(n)]\mathcal{PCP}[f(n),g(n)]MM.ZA\mathcal{MA}fa( n )fa(n)f(n)sol( n …
1
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 …
2
Krajobraz interaktywnych systemów dowodowych
Moje pierwsze pytanie dotyczy tego, czy charakterystyka interaktywnego systemu dowodu jest znana dla wszystkich klasycznych klas złożoności. Nazwałbym P, NP, PSPACE, EXP, NEXP, EXPSPACE, funkcje rekurencyjne i rekurencyjnie wyliczalne klasyczne (między innymi). W szczególności, czy charakterystyka interaktywnego systemu dowodu znana jest z funkcji rekurencyjnych i rekurencyjnie wyliczalnych? Wiem tylko, że …
1
Co wiadomo na temat interaktywnych proofów z wieloma dowodami z krótkimi wiadomościami?
Beigi, Shor i Watrous mają bardzo ładny artykuł na temat mocy kwantowych dowodów interaktywnych z krótkimi wiadomościami. Rozważają trzy warianty „krótkich wiadomości”, a konkretny, na którym mi zależy, to ich drugi wariant, w którym można wysłać dowolną liczbę wiadomości, ale całkowita długość wiadomości musi być logarytmiczna. W szczególności pokazują, że …
1
Jak zdefiniować funkcję indukcyjnie na podstawie dwóch argumentów w Coq?
Jak przekonać Coq, że podana poniżej funkcja rekurencyjna kończy się? Funkcja przyjmuje dwa argumenty indukcyjne. Intuicyjnie rekursja kończy się, ponieważ którykolwiek argument jest rozkładany. W szczególności funkcja przyjmuje dwa drzewa jako dane wejściowe. Inductive Tree := | Tip: Tree | Bin: Tree -> Tree -> Tree. Na drzewach lubię stosować …
2
Interaktywny dowód liczby Boga?
Ostatnio uczyłem się o interaktywnych dowodach i zastanawiałem się, czy cała ta sprawa była jedynie ciekawostką teoretyczną, czy też miała jakieś praktyczne zastosowania. Myślałem, że zacznę od przykładu, który przyszedł mi do głowy pod prysznicem: Ostatnio ogłaszano, że „liczba Boga” = 20. (Liczba Boga to minimalna liczba kroków potrzebnych do …
1
Równoważność dwóch definicji kompletności i solidności w interaktywnych systemach dowodowych
Kompletność i solidność w interaktywnych systemach dowodowych są nieformalnie definiowane jako: Kompletność: Jeśli stwierdzenie jest prawdziwe, szczery Prover może przekonać uczciwego weryfikatorem tego faktu WHP . Poprawność: jeśli oświadczenie jest fałszywe, oszust nie może przekonać uczciwego weryfikatora (o ważności fałszywego oświadczenia) Termin „bicz” jest albo interpretowany jako „z prawdopodobieństwem większym …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.