Czy wiadomo, czy

Odwrotne włączenie jest oczywiste, podobnie jak fakt, że każdy samonredukowalny język NP w BPP jest również w RP. Czy znane jest to również w przypadku języków NP nieredukowalnych?

Jak w przypadku większości złożonych pytań, nie jestem pewien, czy pełna odpowiedź będzie dostępna przez bardzo długi czas. Ale możemy przynajmniej wykazać, że odpowiedź nie ma charakteru relatywistycznego: istnieje wyrocznia, w odniesieniu do której utrzymuje się nierówność, i jedna, w stosunku do której utrzymuje się równość. Dość wyrocznia, w stosunku do której klasy są równe, jest dość łatwa: każda wyrocznia, która ma będzie działać (np. Każda wyrocznia, w stosunku do której „losowość niewiele pomaga”), ponieważ będzie każda wyrocznia, która ma (np. każda wyrocznia, w stosunku do której „losowość bardzo pomaga”). Jest ich wiele, więc nie zawracam sobie głowy szczegółami.$\mathrm{BPP} = \mathrm{RP}$$\mathrm{NP} \subseteq \mathrm{BPP}$

Trochę trudniejsze, choć wciąż dość proste, jest zaprojektowanie wyroczni, do której otrzymamy . Poniższa konstrukcja faktycznie działa trochę lepiej: dla każdej stałej istnieje wyrocznia, względem której istnieje język w którego nie ma w . Przedstawię to poniżej.$\mathrm{RP} \subsetneq \mathrm{BPP} \cap \mathrm{NP}$$c$$\mathrm{coRP} \cap \mathrm{UP}$$\mathrm{RPTIME}[2^{n^c}]$

Zaprojektujemy wyrocznię która zawiera łańcuchy postaci , gdzie jest łańcuchem bitowym, jest pojedynczym bitem, a jest łańcuchem bitowym o długości . Podamy również język który zostanie ustalony przez maszynę i maszynę w następujący sposób:$A$$(x,b,z)$$x$$n$$b$$z$$2n^c$$L^A$$\mathrm{coRP}$$\mathrm{UP}$

• Maszyna na wejściu losowo zgaduje o długości , wysyła zapytania i kopiuje odpowiedź.$\mathrm{coRP}$$x$$z$$2|x|^c$$(x,\mathtt{0},z)$
• Maszyna na wejściu zgaduje o długości , wysyła zapytania i kopiuje odpowiedź.$\mathrm{UP}$$x$$z$$2|x|^c$$(x,\mathtt{1},z)$

Aby wyżej wymienione maszyny rzeczywiście spełniały swoje obietnice, potrzebujemy aby spełnić niektóre właściwości. Dla każdego musi występować jedna z tych dwóch opcji:$A$$x$

• Opcja 1: co najwyżej połowę wyboru mają i zerowe wyboru mają . (W tym przypadku )$z$$(x,\mathtt{0},z) \in A$ $z$$(x,\mathtt{1},z) \in A$$x \not\in L^A$
• Wariant 2: Każdy wyboru jest i dokładnie jeden wyboru jest . (W tym przypadku )$z$$(x,\mathtt{0},z) \in A$ $z$$(x,\mathtt{1},z) \in A$$x \in L^A$

Naszym celem będzie określenie spełniającego te obietnice, dzięki czemu przekątna względem każdej maszyny . Aby spróbować skrócić tę i tak już długą odpowiedź, porzucę maszynę do budowy wyroczni i wiele nieistotnych szczegółów i wyjaśnię, jak przekątnie na konkretnej maszynie. Fix randomizowane maszyny Turinga, niech być wejściowego tak, że mają pełną kontrolę nad wyborem 's i jest takie, że . Złamiemy na .$A$$L^A$$\mathrm{RPTIME}[2^{n^c}]$$M$$x$$b$$z$$(x,b,z) \in A$$M$$x$

• Przypadek 1: Załóżmy, że istnieje sposób na wybranie , aby spełniał pierwszą opcję swojej obietnicy, a ma wybór losowości, który akceptuje. Następnie przydzielimy do tego wyboru. Wtedy nie może jednocześnie spełnić obietnicy i odrzucić . Niemniej jednak, . Mamy więc diagonalized przeciwko .$z$$A$$M$$A$$M$$\mathrm{RP}$$x$$x \not\in L^A$$M$

• Przypadek 2: Następnie załóżmy, że poprzedni przypadek nie zadziałał. Pokażemy teraz, że wtedy może być zmuszony albo do złamania obietnicy albo do odrzucenia po wybraniu spełniającego drugą opcję jego obietnicy. Ten diagonalizes przeciwko . Zrobimy to w dwóch krokach:$M$$\mathrm{RP}$$A$$M$

  1. Pokazują, że dla każdego ustalonego wyboru z jest przypadkowych bitów należy odrzucić, gdy wszystkie jej zapytań postaci są i wszystkie jego zapytań postaci nie są .$r$$M$$M$$(x,\mathtt{0},z)$$A$$(x,\mathtt{1},z)$$A$
  2. Pokaż, że możemy przerzucić odpowiedź na dla pewnego wyboru bez znaczącego wpływu na prawdopodobieństwo przyjęcia$(x,\mathtt{1},z)$$A$$z$$M$

  Rzeczywiście, jeśli zaczniemy od od kroku 1, prawdopodobieństwo przyjęcia wynosi zero. nie do końca spełnia drugą opcję swojej obietnicy, ale możemy następnie przerzucić jeden bit, jak w kroku 2 i tak się stanie. Ponieważ przerzucenie bitu powoduje , że prawdopodobieństwo akceptacji pozostaje bliskie zeru, wynika z tego, że nie może jednocześnie zaakceptować i spełnić obietnicy .$A$$M$$A$$M$$M$$x$$\mathrm{RP}$

Pozostaje argumentować dwa kroki w przypadku 2:

1. Zamocować do wyboru losowego bitów dla . Symulowany pomocą jako przypadkowość oraz odpowiadania na pytania, tak że i . Zauważ, że wykonuje maksymalnie zapytań. Ponieważ istnieją wyborów , możemy naprawić niezbite wybory aby mieć i mieć nadal spełniające pierwszą opcję jego obietnica. Ponieważ nie mogliśmy sprawić, aby Przypadek 2 działał dla , oznacza to, że$r$$M$$M$$r$$(x,\mathtt{0},z) \in A$$(x,\mathtt{1},z) \not\in A$$M$$2^{n^c}$$2^{2n^c}$$z$$z$$(x,\mathtt{0},z) \not\in A$$A$$M$$M$musi odrzucić wszystkie wybrane losowości względem , w szczególności . Wynika z tego, że jeśli wybierzemy aby mieć i dla każdego wyboru , to dla każdego wyboru od przypadkowych bitów , odrzuca względem .$A$$r$$A$$(x,\mathtt{0},z) \in A$$(x,\mathtt{1},z) \not\in A$$z$$r$$M$$A$

2. Załóżmy, że dla każdego ułamek losowych bitów, dla których zapytań wynosi co najmniej . Zatem łączna liczba zapytań wynosi co najmniej . Z drugiej strony dokonuje co najwyżej zapytań we wszystkich swoich gałęziach, co jest sprzecznością. Dlatego istnieje wybór tak aby ułamek losowych bitów, dla których zapytań był mniejszy niż 1/2. Odrzucenie wartości na tym łańcuchu wpływa zatem na prawdopodobieństwo przyjęcia o mniej niż .$z$$M$$(x,\mathtt{1},z)$$1/2$$2^{2n^c} 2^{2^{n^c}}/2$$M$$2^{2^{n^c}} 2^{n^c}$$z$$M$$(x,\mathtt{1},z)$$A$$M$$1/2$

Nie, nie wiadomo. To może nie być najbardziej przekonujący dowód, ale spójrz na tę wyszukiwarkę Google .