pod względem

15

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.[fa(n),sol(n)]M.ZAfa(n)sol(n)

Jednak w 1990 r. Babai, Fortnow i Lund udowodnili, że , więc nie jest to dokładnie ograniczenie. Jakie są parametry ( f ( n ) , g ( n ) ), dla których P C P [ f ( n ) , g ( n )P.doP.[poly(n),poly(n)]=N.miXP.fa(n),sol(n) ?P.doP.[fa(n),sol(n)]=M.ZA

Piękność
źródło

Odpowiedzi:

18

Jeśli chcesz przekształcić definicję MA w kategoriach PCP, potrzebujesz innego parametru dla PCP, a mianowicie długości dowodu. MA jest wyraźnie taki sam jak PCP z losowością wielomianową, zapytaniami wielomianowymi i dowodami wielomianowymi. Zwykle długość dowodu w PCP nie jest ograniczona (to znaczy jest ograniczona pośrednio losowością i zapytaniami), ale jest to niewystarczające, aby przekształcić definicję MA.

Jeśli szukasz jakiejś charakterystyki postaci MA = PCP ( q ( n ), r ( n )), która nie jest jedynie powtórzeniem definicji MA, to nie sądzę, aby taka charakterystyka była znana.

Tsuyoshi Ito
źródło
11

Na podstawie założenia, twardości, to znaczy, że klasa złożoność wymaga obwody wykładniczej rozmiar wystarcza, aby derandomize M A tak, że M = N P . W rzeczywistości derandomizacja ma na celu wykazanie, że B P P = P (patrz Impagliazzo-Wigderson lub Sudan-Trevisan-Vadhan). Ponieważ jednak w M A weryfikatorem jest maszyna B P P , możemy ją zastąpić maszyną deterministyczną.mi=reT.jaM.mi(2)O(n))M.ZAM.ZA=N.P.bP.P.=P.M.ZAbP.P.

W ten sposób, twardość modulo to założenie, powinien mieć taką samą charakterystykę PCP N P . Społeczność złożoności wydaje się mocno wierzyć, że założenie dotyczące twardości jest również prawdziwe.M.ZAN.P.

Edit: Warto również spojrzeć na Andy'ego Druckera Masters pracy: „A PCP Charakterystyka ”: http://eccc.hpi-web.de/report/2010/019/ .ZAM.

Impagliazzo-Wigderson: http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IW97/proc.pdf

Sudan-Trevisan-Vadhan: http://www.cs.berkeley.edu/~luca/pubs/stv-full.ps

Henry Yuen
źródło
11

Tsuyoshi Ito odpowiedział dosłownie na pytanie, ale chciałem skomentować semantykę magisterskich i PCP i ich różnic.

MA jest probabilistyczną wersją NP, tzn. Weryfikator może również wykorzystywać wiele losowych bitów.

W PCP możemy odnosić się do „losowości” weryfikatora, ale zwykle losowość jest logarytmiczna w czasie działania weryfikatora, tzn. Weryfikator mógł sam wypróbować wszystkie możliwe ciągi losowe. Innymi słowy, ta „losowość” nie kupuje weryfikatorowi żadnej mocy obliczeniowej, w przeciwieństwie do MA.

[Więc do czego służy ta „losowość”? Chodzi o to, że do weryfikacji probabilistycznej wystarczy jeden test - ze stałą liczbą zapytań do dowodu - wystarczy]

Dodatek (zgodnie z komentarzem Tsuyoshi): W parametrach NPP w czasie rzeczywistym weryfikator może być wykonany jako logarytmiczny, i podobnie w charakterystykach NEXP, czas działania weryfikatora jest wielomianowy. Niemniej jednak losowość w konstrukcjach PCP jest zwykle wykorzystywana tylko do wybrania testu (w charakterystyce NP, z wielu testów i w charakterystyce NEXP, z wykładniczo wielu), a nie do pomocy w obliczeniach. Ponadto w MA dowód ma wielkość wielomianową, podczas gdy w charakterystyce NEXP dowód ma wielkość wykładniczą.

Dana Moshkovitz
źródło
Zgadzam się, że podajemy weryfikatorowi tylko losowość logarytmiczną w twierdzeniu PCP dla NP, tak że sama losowość nie kupi weryfikatorowi żadnej mocy obliczeniowej. Wydaje się jednak, że wysunąłeś bardziej ogólne twierdzenie, stwierdzając, że „zazwyczaj losowość jest logarytmiczna w czasie działania weryfikatora”, co, obawiam się, jest zbyt ogólne, aby mogło być prawdziwe. Zwykle nie pozwalamy weryfikatorowi spędzać wykładniczego czasu, nawet jeśli weźmiemy pod uwagę PCP (poli, poli) = NEXP (chociaż to nie zmienia tej równości), i wydaje się, że jest to kontrprzykład na twoje oświadczenie.
Tsuyoshi Ito,
1
Dzięki za kontynuację! Myślę, że teraz rozumiem lepiej, co masz na myśli mówiąc, że MA i PCP inaczej stosują losowość.
Tsuyoshi Ito,