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 ).$\mathcal{PCP}[f(n),g(n)]$$\mathcal{MA}$$f(n)$$g(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 $\mathcal{PCP}[poly(n), poly(n)] = \mathcal{NEXP}$$f(n),g(n)$ ?$\mathcal{PCP}[f(n), g(n)] = \mathcal{MA}$

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.

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ą.$E = DTIME(2^{O(n)})$$MA$$MA = NP$$BPP = P$$MA$$BPP$

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.$MA$$NP$

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

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

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ą.