BPP (złożoność) – Wikipedia

W teorii złożoności obliczeniowej, BPP ( Ograniczony problem probabilistyczny wielomianowy , „Probabilistyczny czas wielomianowy z ograniczonym błędem”) to klasa złożoności, do której należą te problemy decyzyjne, które wymagają czasu wielomianowego, aby mieć prawidłowe rozwiązanie probabilistyczne. Mówiąc dokładniej, można je rozwiązać w czasie wielomianowym przez probabilistyczną maszynę Turinga, z prawdopodobieństwem błędu do maksymalnie 1/3 dla wszystkich instancji.

Algorytm BPP (1 wykonanie)
	Wyprodukowana odpowiedź
Odpowiedź prawidłowy	TAK	NIE
TAK	≥ 2/3	≤ 1/3
NIE	≤ 1/3	≥ 2/3
Algorytmo BPP ( k wykonania)
	Wyprodukowana odpowiedź
Odpowiedź prawidłowy	TAK	NIE
TAK	> 1 – 2 – ck	<2 – ck
NIE	<2 – ck	> 1 – 2 – ck
dla pewnej stałej C > 0

Nieformalnie problem dotyczy BPP, jeśli istnieje algorytm, który ma następujące właściwości:

• Monety są dozwolone i podejmują losowe decyzje
• Gwarantuje, że jest wykonywany w czasie wielomianowym
• W dowolnym dniu wykonania algorytmu ma bardziej prawdopodobne 1/3 prawdopodobieństwa udzielenia niewłaściwej odpowiedzi, czy odpowiedź jest tak, czy nie.

BPP ma największe „praktyczne” klasy problemów, tj. Większość problemów zainteresowania BP ma wydajne algorytmy probabilistyczne, które można wykonać na prawdziwych nowoczesnych maszynach. Z tego powodu jest to bardzo praktyczne zainteresowanie, które problemy i klasy problemy znajdują się w BPP. BPP zawiera również P, klasę problemów, które można rozwiązać w czasie wielomianowym za pomocą maszyny deterministycznej, ponieważ maszyna deterministyczna jest szczególnym przypadkiem maszyny probabilistycznej.

W praktyce prawdopodobieństwo błędu 1/3 może nie być akceptowalne, jednak wybór 1/3 w definicji jest arbitralny. Może to być dowolna stała między 0 a 1/2 (wyłączna), a zestaw BPP nie będzie się zmienił. Nie może być nawet stałe: definiuje się tę samą klasę problemów, umożliwiając wysoki błąd do 1/2 – N ^{– C} Z jednej strony lub wymaganie niewielkiego błędu do 2 ^{– N C} z drugiej strony, gdzie C To każda pozytywna stała, ed N Jest to długość Aput. Chodzi o to, że istnieje prawdopodobieństwo błędu, ale jeśli algorytm jest wykonywany wiele razy, możliwość, że większość egzekucji jest błędna wykładniczo w wyniku ograniczenia Chernoffa. ^[Pierwszy] Umożliwia to stworzenie niezwykle dokładnego algorytmu, po prostu wykonując algorytm kilka razy i przyjmując „większość głosów” odpowiedzi. Na przykład, jeśli klasa została zdefiniowana z ograniczeniem, że algorytm może być błędny z maksymalnie 1/2 ¹⁰⁰ , spowodowałoby to tę samą klasę problemów.

Język L Jest w BPP, jeśli i tylko wtedy, gdy istnieje probabilistyczna maszyna Turinga M , takie

• M Działa przez czas wielomianowy na wszystkich wejściach
• Dla wszystkich X W L W M emituje 1 z prawdopodobieństwem większym lub równym 2/3
• Dla wszystkich X nie w L W M emituje 1 z prawdopodobieństwem mniejszym lub równym 1/3

W przeciwieństwie do klasy złożoności ZPP, maszyna jest wymagana M Funkcje czasu wielomianowego na wszystkich wejściach, niezależnie od wyniku losowych premier monet.

Alternatywnie BPP można zdefiniować przy użyciu tylko deterministycznych maszyn Turinga. Język L Jest w BPP, jeśli i tylko wtedy, gdy jest czas wielomianowy P i maszyna deterministyczna Turinga M , takie

• M Działa przez czas wielomianowy na wszystkich wejściach
• Dla wszystkich X W L , wioska sznurków I długości P (| X |) To satysfakcjonuje M (x, y) = 1 jest większy lub równy 2/3
• Dla wszystkich X nie w L , wioska sznurków I długości P (| X |) To satysfakcjonuje M (x, y) = 1 i mniej lub równe 1/3

W tej definicji ciąg I Odpowiada to wyniku losowych uruchomień monet, które zrobiłby probabilistyczna maszyna Turinga. W przypadku niektórych aplikacji ta definicja jest preferowana, ponieważ nie wspomina o probabilistycznych maszynach Turinga.

Oprócz problemów w P, które są oczywiście w BP, wiele problemów znano w BP, ale nie w P. liczba tych problemów maleje, a przypuszczenie p = BPP.

Przez długi czas jednym z najsłynniejszych problemów, o których wiadomo, że znajdowały się w BP, ale nie bycie w P był problem ustalenia, czy liczba jest pierwsza. Jednak w eseju z 2002 roku Program jest w P. , Manindra Agrawal i jej studenci Neeraj Kayal i Nitin Saxena znaleźli deterministyczny algorytm czasu na ten problem, co pokazuje, że jest on w P.

Ważnym przykładem problemu w BPP (faktycznie w CO-RP), który nie jest jeszcze znany w P, jest weryfikacja tożsamości wielomaru, problem ustalenia, czy wielomian jest identyczny równy zerowej wielomianowi. Innymi słowy, czy istnieje przypisanie zmiennych, tak że po obliczaniu wielomianu, czy wynik jest inny od zera? Wystarczy wybrać wartość każdej zmiennej losowo losowo przez przynajmniej podsetek D wartości w celu uzyskania krzesła o błędach wiązania, gdzie D Jest to całkowity stopień wielomianu. ^[2]

Jeśli usuniesz dostęp do losowości z definicji BPP, otrzymujemy klasę złożoności P. Przy zdefiniowaniu klasy, jeśli zastąpimy wspólną maszynę Turing komputerem kwantowym, otrzymujemy klasę BQP.

Dodaj post -sekundę do BPP lub pozwól, aby trasy obliczeniowe mają różne długości, podaj klasę BPP _ścieżka . ^[3] Wiadomo, że BPP _ścieżka Zawiera NP i jest zawarty w swoim odpowiedniku kwantowym poBQP.

Algorytm Monte Carlo jest losowym algorytmem, który jest prawdopodobny, jest poprawny. Problemy w klasie BPP mają algorytmy Monte Carlo z powiązanym wielomianowym czasem wykonania. Jest to konfrontowane z algorytmem Las Vegas, który jest randomizowanym algorytmem, który emituje prawidłową odpowiedź lub emituje „bankructwo” z niskim prawdopodobieństwem. Algorytmy Las Vegas z czasami wykonania z ograniczeniem wielomianowym są używane do zdefiniowania klasy ZPP. Alternatywnie, ZPP zawiera algorytmy probabilistyczne, które są zawsze prawidłowe i mają oczekiwany czas wykonywania wielomianowego. Jest to słabsze niż powiedzenie, że jest to algorytm w czasie wielomianowym, ponieważ może działać przez czas wielomianowy, ale z bardzo niskim prawdopodobieństwem.

Wiadomo, że BPP jest zamknięty pod komplementem; To znaczy, BPP = Co-CPP. BPP sam w sobie jest niski, co oznacza, że ​​maszyna BPP o mocy do natychmiastowego rozwiązywania problemów BPP (maszyna Oracle BPP) nie jest mocniejsza niż maszyna bez tej dodatkowej mocy. W symboli, BPP ^BPP = BPP.

Związek między BPP i NP jest nieznany: nie wiadomo, czy BPP jest podzbiorem NP, NP jest podzbiorem BPP lub jeśli są nieporównywalne. Jeśli NP jest zawarty w BPP, co jest uważane za mało prawdopodobne, ponieważ oznaczałoby to praktyczne rozwiązania problemów NP, wówczas NP = RP i PH ⊆ BPP. ^[4]

Wiadomo, że RP jest podzbiorem BPP, a BPP jest podzbiorem PP. Nie wiadomo, czy te dwa są dwoma wąskimi podzbiorami, ponieważ nawet nie wiemy, czy P jest wąskim podzbiorem Pspace. BPP jest zawarty na drugim poziomie hierarchii wielomianowej i dlatego jest zawarty w pH. Mówiąc dokładniej twierdzenie Sipsser-Lauonmann

${DisplayStyle Bppsubseteq Sigma _ {2} cap pi _ {2}}$

. W rezultacie p = NP prowadzi do p = bpp, ponieważ pH zapada się do p w tym przypadku. Zatem o p = bpp lub p ☎ np lub oba.

Twierdzenie Adlemana stwierdza, że ​​przynależność do dowolnego języka w BPP może być określona przez rodzinę obwodów logicznych o wielkości wielomianowej, co oznacza, że ​​BPP jest zawarty w P/Pol. ^[5] W rzeczywistości, w wyniku demonstracji tego faktu, każdy algorytm BPP, który działa przy wejściu do przychodów, może być obłąkany w algorytmie deterministycznym, który wykorzystuje stały ciąg losowych bitów. Znalezienie tego ciągu może być jednak drogie.

W odniesieniu do wyroczni wiemy, że istnieją wyrogi a i b, takie, że p ^A = BPP ^A e p ^B ≠ BPP ^B . Ponadto, w odniesieniu do losowej wyroczni z prawdopodobieństwem 1, p = BP i BPP jest ściśle zawarty w NP i CO-NP. ^[6]

Istnienie niektórych silnych generatorów liczb losowych jest przypuszczane przez większość ekspertów terenowych. Ta przypuszczenie oznacza, że ​​losowość nie daje dodatkowej mocy obliczeniowej obliczeniowej w czasie wielomianowym, to znaczy p = rp = bpp. Zauważ, że wspólne generatory nie wystarczą, aby pokazać ten wynik; Każdy algorytm probabilistyczny, że używa typowego generatora generatora losowego, zawsze daje nieprawidłowe wyniki na niektórych danych wejściowych niezależnie od nasienia (chociaż te wejścia mogą być rzadkie).

László Babai, Lance Fortnow, Noam Nisan i Avi Wigderson pokazali, że jeśli Exptime nie upadnie do, ale BPP jest zawarty w ^[7]

${DisplayStyle Mathbf {i.o.-subexp} = bigcap noliMits _ {varepsilon> 0} mathbf {i.o.-dime} lewy (2^{n^{varepsilon}} po prawej).}$

${DisplayStyle Mathbf {e} = Mathbf {dtime} po lewej (2^{o (n)} po prawej),}$

ma złożoność obwodów 2 ^{Oh ( N )} Następnie p = BPP. ^[8]

• Valentine Kabanets (2003). „CMPT 710 – Teoria złożoności: wykład 16”. Simon Fraser University.
• Christos Papadimitriou, Złożoność obliczeniowa , 1. edycja, Addison Wesley, 1993, ISBN 0-201-53082-1. pp. 257–259 w sekcji 11.3: „Losowe źródła”. pp. 269–271 sekcji 11.4: „Złożoność obwodu”.
• Michael Sipser, Wprowadzenie do teorii obliczeń , PWS Publishing, 1997, ISBN 0-534-94728-X. Sekcja 10.2.1: „Klasa BPP, s. 336–339”.