Czy dla losowej wyroczni R BPP równa się zestawowi języków obliczeniowych w P ^ R?


18

Cóż, tytuł prawie wszystko mówi. Interesujące pytanie powyżej zostało zadane przez komentatora Jaya na moim blogu (patrz tutaj i tutaj ). Zgaduję, że odpowiedź brzmi „tak” i że istnieje stosunkowo prosty dowód, ale nie widziałem go od razu. (Jednak z grubsza można by próbować pokazać, że jeśli język w nie był w , to musiałby mieć nieskończoną algorytmiczną wzajemną informację z , w którym to przypadku nie byłby obliczalny. Należy również pamiętać, że jeden kierunek jest trywialny: języki obliczeniowe w pewnością zawierają ).PRBPPRPR BPP

Zauważ, że nie pytam o klasę AlmostP , która składa się z tych języków, które są w dla prawie każdego (i jest dobrze znane z równego ). Na to pytanie, musimy najpierw naprawić , a następnie spojrzeć na zestaw języków obliczalnych w . Z drugiej strony, może próbować pokazują, że gdy język, w jest obliczeniowy, nawet na nieruchomej losowo oracle , to w rzeczywistości, że język musi znajdować się w A l m O a T P .PRRBPPRPRPRRAlmostP

Ściśle powiązane pytanie brzmi, czy z prawdopodobieństwem 1 w stosunku do losowej wyroczniR mamy

AM=NPRComputable.

Jeśli tak, to otrzymujemy następującą interesującą konsekwencję: jeśli , to z prawdopodobieństwem 1 przypadkowej wyroczni R , jedynymi językami, które są świadkami separacji wyroczni P RN P R, są języki nieobliczalne.P=NPRPRNPR


1
Jest kilka powiązanych artykułów Erica Allendera i jego współautorów: Ograniczenia mocy obliczeniowej losowych ciągów , Redukcje do zbioru losowych ciągów: Sprawa ograniczona zasobami
Kaveh

Odpowiedzi:


16

Tak.

Po pierwsze, ponieważ zajęło mi chwilę, aby dowiedzieć się tego ja, niech mi sformalizować różnicę między pytaniem a ; jest to kolejność kwantyfikatorów. A l m o s t P : = { L : P r R ( L P R ) = 1 } , a wynikiem, o którym wspominasz, jest LAlmostPAlmostP:={L:PrR(LPR)=1} . Jeśli dobrze zrozumiałem, pytasz, czy P r R ( LLLBPPPrR(LPR)=1 .PrR(LLPRCOMPLBPP)=PrR(PRCOMP=BPP)=1

Rozważać

.p:=1PrR(PRCOMP=BPP)=PrR(LPRCOMPBPP)

W związku związkowym jest ograniczone górną granicą przez L C O M P P r R ( L P RB P P ) . (Zauważ, że ta ostatnia suma jest policzalna.) Teraz, zgodnie z prawem 0-1 - które ma zastosowanie, ponieważ wszystkie odpowiednie stwierdzenia nie zmieniają się, jeśli ostatecznie zmienimy R - każde prawdopodobieństwo w tej sumie wynosi 0 lub 1. Jeśli odpowiedź na twoje pytanie brzmi: nie, to p = 1 , więc musi być trochę L C O M P, takich jakpLCOMPPrR(LPRBPP)Rp=1LCOMP . Lecz to fakt, że l m O a T P = B P P .PrR(LPRBPP)=1AlmostP=BPP

Aktualizacja 10 październik 2014 : Jak wskazano w komentarzu Emil Jeřábek, to samo odnosi się do argumentu wobec N P R , ponieważ również, że l m O a T N P = M .AMNPRAlmostNP=AM

Wskazuje również, że nie używaliśmy niczego o poza tym, że jest to klasa policzalna, która zawiera B P P (odpowiednio, A M ). Więc „interesujący wniosek” w OQ rzeczywiście odnosi się do dowolnej policzalnych klasy języków C , który zawiera A M : jeśli P = N P , to „tylko” Języki, w których świadek separacja wyrocznia P RN P R są poza CCOMPBPPAMCAMP=NPPRNPRC. Ale to ostatnie stwierdzenie wydaje mi się nieco mylące (wydaje się, że dla każdego możemy rozważyć C = A M{ L 0 } , a tym samym „pokazać”, że żaden L 0 nie realizuje N P RP R , sprzeczne ze znanym twierdzeniem). Raczej pisząc to symbolicznie, pokazaliśmy:L0C=AM{L0} L0NPRPR

Jeśli , to policzalne  CA MP=NP .countable CAMPrR(NPRPR and NPRC=PRC)=1

Należy zauważyć, że ważne, prawdopodobieństwo 1 nie jest to to samo, co wszystkich i które pełnej środek zestaw R spełniałby argumentem P r R może zależeć od C . Więc jeśli spróbujemy zmienić C na C{ L 0 } , to co najwyżej usunie zestaw R miary 0, który spełnia tę instrukcję.RRPrRdodoC{L0}R


5
Ten sam argument dotyczy AM vs NP ^ R. Również obliczalność nie ma tak naprawdę znaczenia, jedyną właściwością języków obliczeniowych użytych w dowodzie jest to, że istnieje ich niezliczona ilość.
Emil Jeřábek wspiera Monikę

7

Chociaż kolejność kwantyfikatorów między pytaniem a prawie P jest różna, nietrudno jest wykazać, że są one równoważne. Po pierwsze, dla każdego ustalonego L pytanie, czy L \ w P ^ O nie zależy od żadnego skończonego początkowego segmentu O. Wynika z tego, że prawdopodobieństwo, że L \ w P ^ R wynosi 0 lub 1. Z prawie - Wynik P, dla każdego obliczalnego L spoza BPP, odpowiedź wynosi 0, natomiast jeśli L \ w BPP, prawdopodobieństwo wynosi 1. Ponieważ istnieje obliczalnie wiele obliczalnych L, możemy wykonać związanie związane; policzalna suma zbiorów prawdopodobieństwa 0 ma prawdopodobieństwo 0. Zatem prawdopodobieństwo, że istnieje jakikolwiek obliczalny L, który nie jest w BPP, ale jest w P ^ R wynosi 0, podobnie jak prawdopodobieństwo, że istnieje język w BPP nie w P ^ R,

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.