Jakie konkretne dowody istnieją dla P = RP?

RP to klasa problemów rozstrzyganych przez niedeterministyczną maszynę Turinga, która kończy się w czasie wielomianowym, ale dopuszczalny jest również błąd jednostronny. P jest zwykłą klasą problemów rozstrzyganych przez deterministyczną maszynę Turinga, która kończy się w czasie wielomianowym.

P = RP wynika z zależności w złożoności obwodu. Impagliazzo i Wigderson wykazali, że występuje P = BPP, jeśli jakiś problem, który można rozstrzygnąć w deterministycznym czasie wykładniczym, również wymaga wykładniczych obwodów wielkości (zauważ, że P = BPP implikuje P = RP). Być może z powodu tych wyników wydaje się, że niektórzy teoretycy złożoności mają wrażenie, że redukcje probabilistyczne mogą być prawdopodobnie zdesandomizowane.

Jakie są inne konkretne dowody na to, że P = RP?

Występowanie problemów w DTIME (2 ^ O (n)), które wymagają obliczeń obwodów wielkości wykładniczej (co jest założeniem w IW), wydaje się prawdopodobne, ponieważ w przeciwnym razie mielibyśmy niejednorodność przyspieszającą KAŻDY problem obliczeniowy - który jest całkowicie sprzeczne z obecnym myśleniem, w którym nie ma „zbyt znaczącej” luki między jednolitą i niejednorodną złożonością dla „normalnych” problemów. Takie myślenie wynika z faktu, że istnieje bardzo niewiele przykładów, w których znany jest algorytm „nierównomierny”, który jest znacznie lepszy niż znany jednolity algorytm (ponownie z wyjątkiem derandomizacji).

Kolejnym „dowodem” jest to, że w stosunku do losowej wyroczni mamy P = BPP.

Każdy konkretny wynik derandomizacji dowodzi, że P = BPP. Jako takie PRIMES w P (Agrawal-Kayal-Saxena'02) jest dobrym przykładem. Ogólnie rzecz biorąc, istnieje kilka naturalnych problemów w BPP, o których nie wiadomo, że są w P (testowanie tożsamości wielomianowej jest jednym znaczącym wyjątkiem).

Hastad-Impagliazzo-Levin-Luby '99 pokazał, że istnienie funkcji jednokierunkowych implikuje istnienie generatorów pseudolosowych. Chociaż nie oznacza to bezpośrednio P = BPP w oparciu o istnienie funkcji jednokierunkowych, pokazuje jednak, że generatory pseudolosowe wynikają z minimalnych założeń kryptograficznych. Może to być postrzegane jako kolejna wskazówka, że ​​BPP nie jest silniejszy niż P.

Ważne jest, aby zauważyć, że powiedzenie „redukcje probabilistyczne mogą [prawdopodobnie] być derandomizowane” jest znacznie silniejsze niż P = RP. W rzeczywistości jedną formalizacją pojęcia derandomizacji wszystkich randomizowanych redukcji jest to, że $P^X=RP^X$ stosunku do każdej wyroczni $X$ , o której wiemy, że jest fałszywa (np. Heller. Relatywizowane hierarchie wielomianowe rozciągające się na dwa poziomy, Teoria systemów matematycznych 17 (2) : 71-84, 1984 daje wyrocznię, w której która nie jest równa P według twierdzenia o hierarchii czasu).$ZPP=RP=EXP$$P$

Powyższe dotyczy oczywiście derandomizacji losowych redukcji wielomianowych Turinga w czasie wielomianowym, a nie zwykłych redukcji wielokrotnych w jednym czasie wielomianowym. Nie zdziwiłbym się, gdyby wyrocznię Hellera można zaadaptować tak, aby uzyskać zestaw X taki, że dla całego Y, Y jest wielokrotnością wykładniczą w czasie wykładniczym wielokrotnością do X i Y Y jest redukowalną RP do X, ale bez przechodzenia przez konstrukcję I nie mogłem tego przysiąc.

Valiant i Vazirani wykazali w 1986 r., Że istnieje losowa redukcja SAT do , która jest problemem decyzyjnym opartym na SAT, w którym liczy się tylko różnica między zadowalającymi i niezadowalającymi przypadkami. Jeśli $USAT_Q$$Q = \bot$$USAT_{\bot}$

$\phi$$\phi$$\phi$$k$$x$$\phi$$k$$x$$k$$x$$k$

$k$$k$$n$$USAT_{\bot}$$n$

$\epsilon > 0$$n^{1-\epsilon}$