W jakiej klasie są algorytmy losowe, które mają błąd z dokładnie 25% szansą?

Załóżmy, że rozważam następujący wariant BPP, który pozwala nam nazywać się E (xact) BPP: Język jest w EBPP, jeśli istnieje wielomianowy losowy czas TG, który akceptuje każde słowo z prawdopodobieństwem dokładnie 3/4 i każde słowo nie w język z prawdopodobieństwem dokładnie 1/4. Oczywiście EBPP jest zawarty w BPP, ale czy są one równe? Czy zostało to zbadane? Co z podobnie definiowanym ERP?

Motywacja. Moją główną motywacją jest to, że chciałem wiedzieć, jaki jest teoretyczny złożoność analogicznego algorytmu losowego `` poprawnej wartości oczekiwanej '' Faenza i in. (patrz http://arxiv.org/abs/1105.4127 ) byłoby. Najpierw chciałem zrozumieć, jakie problemy decyzyjne taki algorytm może rozwiązać (w najgorszym przypadku wielomianowy czas działania). Oznaczmy tę klasę przez E (xpected) V (alue) PP. Łatwo zauważyć, że USAT $\in$ EVPP. Łatwo też zauważyć, że EBPP EVPP. To była moja motywacja. Wszelkie opinie na temat EVPP są również mile widziane.$\subset$

W rzeczywistości ich algorytm zawsze generuje liczbę nieujemną. Jeśli oznaczymy problemy decyzyjne rozpoznawane przez taki algorytm przez EVP (ositive) PP, wówczas nadal mamy USAT EVPPP. Chociaż EBPP może nie być podzbiorem EVPPP, mamy ERP EVPPP. Być może za ich pomocą możemy zdefiniować (nieujemną) rangę problemów decyzyjnych.$\in$$\subset$

Na marginesie, nie jest jasne, czy EBPP jest solidną klasą. Na przykład, jeśli zamiast pozwolić algorytmowi na rzut monetą bezstronną, jeśli otrzyma się bezstronną monetę 3-stronną lub kostkę 6-stronną, nie jest jasne, czy otrzymujesz tę samą klasę. BPP pozostaje taki sam, jeśli zmienisz te dane.

W każdym razie twoim podstawowym pytaniem jest, czy EBPP jest równy BPP, czy nie. Wydaje mi się, że EBPP jest bliższy P niż BPP. Rozważ złożoność kwerendy lub wersję Oracle tych klas, w których mają one dostęp do dużego ciągu wejściowego i muszą zadawać zapytania, aby poznać bity tego ciągu. Jeżeli algorytm P, oblicza się funkcję z Q zapytań, po czym istnieje ścisła stanowiących wielomianem stopnia Q do F na badania . (Jest to zwykły argument metody wielomianowej.) Z drugiej strony, jeśli masz algorytm BPP, to otrzymujesz wielomian stopnia Q nad R, który jest zbliżony do $f$$Q$$Q$$f$$\mathbb{R}$$Q$$\mathbb{R}$$f$w tym sensie, że jego wartość jest zbliżona do wartości na każdym wejściu.$f$

Biorąc pod uwagę algorytm EBPP dla funkcji , możemy zbudować wielomian, który wyprowadza 1/4, gdy odpowiedź brzmi NIE, i 3/4, gdy odpowiedź brzmi TAK. Odejmując 1/2 i mnożąc przez 2, możesz uzyskać dokładnie reprezentujący wielomian, tak jak w przypadku P. To sugeruje mi, że EBPP jest bliższy P.$f$

Ta obserwacja może być również wykorzystana do wykazania separacji wyroczni między EBPP i BPP. Zastanów się nad problemem Obietnica - większość, w którym obiecano, że dane wejściowe mają więcej niż 2 N / 3 1s lub mniej niż N / 3 1s i musisz zdecydować, co się dzieje. Wyraźnie widać to w BPP. Korzystając z opisanego powyżej argumentu wielomianowego, można wykazać, że ta funkcja wymaga zapytań dla maszyny EBPP. Ale zauważ, że możesz również udowodnić separację wyroczni w inny sposób, między P i EBPP. Więc może wyniki wyroczni niewiele mówią o tym problemie? A może mówią, że ciężko będzie wykazać równość w obu kierunkach.$\Omega(N)$

Jeśli chodzi o separacje wyroczni, istnieje wyrocznia z EBPP = BPP = EXP ^NP , a wyrocznia z P = ⊕P (a zatem EBPP = P) i BPP = EXP ^NP .

Jedną z konstrukcji BPP = EXP ^NP wyrocznia (w tym ta z artykułu w Wikipedii BPP ) jest wybranie relatywizowanego pełnego problemu EXP ^NP i kontynuowanie rekurencji w odniesieniu do wielkości wejściowej (dla tego problemu), poprawianie wyników dla wystąpień problemów tego rozmiaru i następnie udziel odpowiedzi na ten problem, jeśli zostanie zapytany o dane wejściowe i wypełniacz (o odpowiedniej długości), który nie został naprawiony. Dla EBPP = EXP ^NP , zamiast prawie zawsze dawać poprawne odpowiedzi, możemy podać tylko tyle błędnych odpowiedzi, aby liczby były prawidłowe. Istnieje również wyrocznia, w której analog błędu zerowego błędu EBPP (dokładnie 1/2 prawdopodobieństwa zgłoszenia awarii) jest równy EXP (i wyrocznia z P = ⊕P, ale ZPP = EXP).

Notowano tutaj wyrocznię P = ⊕P i BPP = EXP ^NP .

Oprócz bycia w BPP i w C ₌ P, EBPP jest w ⊕P, ponieważ możemy zmniejszyć prawdopodobieństwo do liczby świadków, a następnie dostosować tę liczbę.

W nierelatywizowanym świecie BPP prawdopodobnie równa się P, ale dowody są jeszcze silniejsze dla EBPP. EBPP zależy od dokładnej liczby ścieżek w sposób, który, chyba że nastąpi nieoczekiwane anulowanie, wydaje się zasadniczo niemożliwy do wykorzystania.

To jest częściowa odpowiedź; może zainspiruje kogoś innego do zapewnienia lepszego. $\newcommand{\EBPP}{\mathsf{EBPP}}$ $\newcommand{\CP}{\mathsf{C}_=\mathsf{P}}$

Klasa jest szczególnym przypadkiem C = P . Myślę, że jeden ze sposobów definiowania C = P jest następujący (zob. Sekcja 2 tego artykułu ). Język L znajduje się w C = P, jeśli istnieje wielomianowy weryfikator czasu V taki, że$\EBPP$$\CP$$\CP$$L$$\CP$$V$

• jeśli jest w L , to Pr w [ V ( x , w )  przyjmuje ] = $x$$L$ i$\Pr_w[V(x, w) \text{ accepts}] = \frac{3}{4}$
• jeśli nie jest w L , to Pr w [ V ( x , w )  akceptuje ] ≠ $x$$L$ .$\Pr_w[V(x, w) \text{ accepts}] \neq \frac{3}{4}$

(Prawdopodobieństwo kompletności może być zasadniczo dowolnym ułamkiem stałym; wybrałem aby pasowało do prawdopodobieństwa podanego w pytaniu).$\frac{3}{4}$

Jeden ze sposobów definiowania jest następujący. Język L jest w E B P P, jeśli istnieje wielomianowy weryfikator czasu V taki, że$\EBPP$$L$$\EBPP$$V$

• jeśli jest w L , to Pr w [ V ( x , w )  przyjmuje ] = $x$$L$ i$\Pr_w[V(x, w) \text{ accepts}] = \frac{3}{4}$
• jeśli nie jest w L , to Pr w [ V ( x , w )  akceptuje ] = $x$$L$ .$\Pr_w[V(x, w) \text{ accepts}] = \frac{1}{4}$