BPP (complessità)

Nella teoria della complessità computazionale, BPP (Bounded-error Probabilistic Polynomial time, "tempo polinomiale probabilistico con errore limitato") è una classe di complessità a cui appartengono quei problemi decisionali che richiedono un tempo polinomiale per avere una soluzione probabilistica corretta. Più precisamente, essi sono risolvibili in tempo polinomiale da una macchina di Turing probabilistica, con una probabilità di errore al massimo di 1/3 per tutte le istanze.

Algoritmo BPP (1 esecuzione)
	Risposta prodotta
Risposta corretta	SÌ	NO
SÌ	≥ 2/3	≤ 1/3
NO	≤ 1/3	≥ 2/3
Algoritmo BPP (k esecuzioni)
	Risposta prodotta
Risposta corretta	SÌ	NO
SÌ	> 1 − 2^−ck	< 2^−ck
NO	< 2^−ck	> 1 − 2^−ck
per una qualche costante c > 0

Informalmente, un problema è in BPP se c'è un algoritmo per esso che ha le seguenti proprietà:

È consentito lanciare monete e prendere decisioni casuali
È garantito che sia eseguito in tempo polinomiale
In qualsiasi data esecuzione dell'algoritmo, esso ha una probabilità al più pari a 1/3 di dare la risposta sbagliata, sia che la risposta sia SÌ oppure NO.

Introduzione

BPP è delle più grandi classi "pratiche" di problemi, vale a dire che la maggior parte dei problemi di interesse in BPP hanno algoritmi probabilistici efficienti che possono essere eseguiti su macchine moderne reali. Per questa ragione è di grande interesse pratico quali problemi e classi di problemi siano all'interno di BPP. BPP contiene anche P, la classe dei problemi risolvibili in tempo polinomiale con una macchina deterministica, dal momento che una macchina deterministica è un caso speciale di una macchina probabilistica.

In pratica, una probabilità di errore di 1/3 potrebbe non essere accettabile, tuttavia, la scelta di 1/3 nella definizione è arbitraria. Può essere qualsiasi costante fra 0 e 1/2 (esclusiva) e l'insieme BPP sarà immutato. Non deve nemmeno essere costante: la stessa classe di problemi è definita consentendo un errore elevato fino a 1/2 − n^−c da un lato, o richiedendo un errore piccolo fino a 2^{−n^c} dall'altro, dove c è una qualsiasi costante positiva, ed n è la lunghezza dell'input. L'idea è che c'è una probabilità di errore, ma se l'algoritmo è eseguito molte volte, la possibilità che la maggior parte delle esecuzioni siano sbagliate cala esponenzialmente come conseguenza del vincolo di Chernoff.^[1] Questo rende possibile creare un algoritmo estremamente accurato semplicemente eseguendo l'algoritmo parecchie volte e prendendo un "voto a maggioranza" delle risposte. Ad esempio, se si è definita la classe con la restrizione che l'algoritmo possa essere sbagliato con probabilità al massimo 1/2¹⁰⁰, questo darebbe luogo alla stessa classe di problemi.

Definizione

Un linguaggio L è in BPP se e solo se esiste una macchina di Turing probabilistica M, tale che

M funziona per un tempo polinomiale su tutte le immissioni
Per tutti gli x in L, M emette 1 con probabilità maggiore o uguale a 2/3
Per tutti gli x non in L, M emette 1 con probabilità minore o uguale a 1/3

Diversamente dalla classe di complessità ZPP, è richiesto che la macchina M funzioni per un tempo polinomiale su tutte le immissioni, indipendentemente dall'esito dei lanci casuali di monete.

Alternativamente, BPP può essere definito usando soltanto macchine di Turing deterministiche. Un linguaggio L è in BPP se e solo se esiste un tempo polinomiale p e una macchina di Turing deterministica M, tali che

M funziona per un tempo polinomiale su tutte le immissioni
Per tutti gli x in L, la frazione di stringhe y di lunghezza p(|x|) che soddisfano M(x,y) = 1 è maggiore o uguale a 2/3
Per tutti gli x non in L, la frazione di stringhe y di lunghezza p(|x|) che soddisfano M(x,y) = 1 è minore o uguale a 1/3

In questa definizione, la stringa y corrisponde al risultato dei lanci casuali di monete che la macchina di Turing probabilistica avrebbe fatto. Per alcune applicazioni questa definizione è preferibile poiché non menziona le macchine di Turing probabilistiche.

Problemi

Oltre ai problemi in P, che sono ovviamente in BPP, si conoscevano molti problemi che erano in BPP ma non in P. Il numero di tali problemi sta diminuendo, e si congettura che P = BPP.

Per molto tempo, uno dei problemi più famosi che si conosceva essere in BPP ma non essere in P era il problema di determinare se un numero dato è primo. Tuttavia, nel saggio del 2002 PRIMES is in P, Manindra Agrawal e i suoi studenti Neeraj Kayal e Nitin Saxena trovarono un algoritmo deterministico in tempo polinomiale per questo problema, dimostrando così che è in P.

Un esempio importante di un problema in BPP (in realtà in co-RP) che ancora non si conosce in P è la verifica dell'identità dei polinomi, il problema di determinare se un polinomio è identicamente uguale al polinomio zero. In altre parole, c'è un'assegnazione di variabili tale che quando si calcola il polinomio il risultato è diverso da zero? È sufficiente scegliere il valore di ciascuna variabile uniformemente a caso da un sottoinsieme finito di almeno d valori per ottenere una probabilità di errore vincolato, dove d è il grado totale del polinomio.^[2]

Classi correlate

Se si rimuove l'accesso alla casualità dalla definizione di BPP, otteniamo la classe di complessità P. Nella definizione della classe, se sostituiamo la macchina di Turing comune con un computer quantistico, otteniamo la classe BQP.

Aggiungere la postselezione a BPP, o consentire ai percorsi di computazione di avere lunghezze diverse, dà la classe BPP_path.^[3] È noto che BPP_path contiene NP, ed è contenuto nella sua controparte quantistica PostBQP.

Un algoritmo Monte Carlo è un algoritmo randomizzato che è probabile sia corretto. I problemi nella classe BPP hanno algoritmi Monte Carlo con tempo di esecuzione polinomiale vincolato. Questo si confronta con un algoritmo Las Vegas, che è un algoritmo randomizzato che emette la risposta corretta, o emette "fallimento" con bassa probabilità. Gli algoritmi Las Vegas con tempi di esecuzione con vincolo polinomiale si usano per definire la classe ZPP. Alternativamente, ZPP contiene algoritmi probabilistici che sono sempre corretti e hanno un tempo di esecuzione polinomiale atteso. Questo è più debole che dire che è un algoritmo in tempo polinomiale, dal momento che può eseguirsi per il tempo polinomiale, ma con probabilità bassissima.

Proprietà della teoria della complessità

Si sa che BPP è chiuso sotto il complemento; cioè, BPP = co-BPP. BPP è basso di per sé, che significa che una macchina BPP con la potenza per risolvere istantaneamente problemi BPP (una macchina a oracolo BPP) non è affatto più potente della macchina senza questa potenza extra. In simboli, BPP^BPP = BPP.

La relazione tra BPP e NP è ignota: non si sa se BPP è un sottoinsieme di NP, NP è un sottoinsieme di BPP o se sono incomparabili. Se NP è contenuto in BPP, il che è considerato improbabile dal momento che implicherebbe soluzioni pratiche per i problemi NP-completi, allora NP = RP e PH ⊆ BPP.^[4]

È noto che RP è un sottoinsieme di BPP, e BPP è un sottoinsieme di PP. Non è noto se questi due siano due sottoinsiemi stretti, dal momento che non sappiamo nemmeno se P sia un sottoinsieme stretto di PSPACE. BPP è contenuto nel secondo livello della gerarchia polinomiale e perciò è contenuto in PH. Più precisamente, il teorema di Sipser-Lautemann afferma che $\ BPP\subseteq \Sigma _{2}\cap \Pi _{2}$ . Come risultato, P = NP conduce a P = BPP dal momento che PH collassa a P in questo caso. Così o P = BPP o P ≠ NP o entrambi.

Il teorema di Adleman afferma che l'appartenenza in qualsiasi linguaggio in BPP può essere determinata da una famiglia di circuiti booleani di dimensione polinomiale, che significa che BPP è contenuto in P/poly.^[5] In effetti, come conseguenza della dimostrazione di questo fatto, ogni algoritmo BPP che opera su entrate di lunghezza vincolata può essere derandomizzato in un algoritmo deterministico che usa una stringa fissa di bit casuali. Trovare questa stringa può essere costoso, tuttavia.

Relativamente agli oracoli, sappiamo che esistono oracoli A e B, tali che P^A = BPP^A e P^B ≠ BPP^B. Inoltre, relativamente all'oracolo casuale con probabilità 1, P = BPP e BPP è strettamente contenuto in NP e co-NP.^[6]

Derandomizzazione

L'esistenza di certi generatori forti di numeri casuali è congetturata dalla maggior parte degli esperti del campo. Questa congettura implica che la casualità non dà la potenza computazionale aggiuntiva alla computazione in tempo polinomiale, cioè, P = RP = BPP. Si noti che i comuni generatori non sono sufficienti a mostrare questo risultato; qualsiasi algoritmo probabilistico implementato che usa un tipico generatore di numeri casuali produrrà sempre risultati scorretti su certi input a prescindere dal seme (benché questi input potrebbero essere rari).

László Babai, Lance Fortnow, Noam Nisan, e Avi Wigderson dimostrarono che a meno che EXPTIME collassi a MA, BPP è contenuto in^[7]

\mathbf {i.o.-SUBEXP} =\bigcap \nolimits _{\varepsilon >0}\mathbf {i.o.-DTIME} \left(2^{n^{\varepsilon }}\right).

La classe i.o.-SUBEXP, che sta per infinitely often SUBEXP, ossia infinitamente spesso SUBEXP, contiene problemi che hanno algoritmi in tempo subesponenziale per infinitamente molte dimensioni dell'input. Essi mostrarono anche che P = BPP se la gerarchia del tempo esponenziale, che è definita in termini della gerarchia polinomiale, e che E come E^PH, collassa a E; tuttavia, si noti che si congettura che la gerarchia del tempo esponenziale di solito non collassi.

Russell Impagliazzo e Avi Wigderson dimostrarono che se un qualsiasi problema in E, dove

\mathbf {E} =\mathbf {DTIME} \left(2^{O(n)}\right),

ha complessità dei circuiti 2^Ω(n) allora P = BPP.^[8]

Note

^ http://www.cs.sfu.ca/~kabanets/cmpt710/lec16.pdf
^ Madhu Sudan e Shien Jin Ong, Advanced Complexity Theory: Lecture 6: Randomized Algorithms, Properties of BPP, Massachusetts Institute of Technology: 6.841/18.405J, 26 febbraio 2003.
^ [1] Archiviato il 5 agosto 2012 in Internet Archive.
^ Computational Complexity: Pulling Out The Quantumness, su weblog.fortnow.com. URL consultato il 6 marzo 2014 (archiviato dall'url originale il 14 marzo 2006).
^ Adleman, L. M., Two theorems on random polynomial time, Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computing, 1978, pp. 75–83.
^ Charles H. Bennett e John Gill, Relative to a Random Oracle A, P^A != NP^A != co-NP^A with Probability 1, in SIAM Journal on Computing, vol. 10, n. 1, 1981, pp. 96–113, ISSN 1095-7111 (WC · ACNP).
^ László Babai, Lance Fortnow, Noam Nisan, e Avi Wigderson (1993). "BPP has simulations in subexponential time unless EXPTIME has publishabke proofs". Computational Complexity, 3:307–318.
^ Russell Impagliazzo and Avi Wigderson (1997). "P = BPP if E requires exponential circuits: Derandomizing the XOR Lemma". Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 220–229. DOI: 10.1145/258533.258590

Bibliografia

Valentine Kabanets (2003). "CMPT 710 – Complexity Theory: Lecture 16". Simon Fraser University.
Christos Papadimitriou, Computational Complexity, 1ª edizione, Addison Wesley, 1993, ISBN 0-201-53082-1. pp. 257–259 della sezione 11.3: "Random Sources". pp. 269–271 della sezione 11.4: "Circuit complexity".
Michael Sipser, Introduction to the Theory of Computation, PWS Publishing, 1997, ISBN 0-534-94728-X. Sezione 10.2.1: "The class BPP, pp. 336–339".

Collegamenti esterni

(EN) Princeton CS 597E: Derandomization paper list, su cs.princeton.edu.
(EN) Harvard CS 225: Pseudorandomness, su courses.fas.harvard.edu. URL consultato il 6 marzo 2014 (archiviato dall'url originale il 5 agosto 2003).

Portale Informatica

Portale Matematica

[1] ttp://www.cs.sfu.ca/~kabanets/cmpt710/lec16.pdf

[2] Madhu Sudan e Shien Jin Ong, Advanced Complexity Theory: Lecture 6: Randomized Algorithms, Properties of BPP, Massachusetts Institute of Technology: 6.841/18.405J, 26 febbraio 2003.

[3] [1] Archiviato il 5 agosto 2012 in Internet Archive.

[4] Computational Complexity: Pulling Out The Quantumness, su weblog.fortnow.com. URL consultato il 6 marzo 2014 (archiviato dall'url originale il 14 marzo 2006).

[5] Adleman, L. M., Two theorems on random polynomial time, Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computing, 1978, pp. 75–83.

[6] Charles H. Bennett e John Gill, Relative to a Random Oracle A, P^A != NP^A != co-NP^A with Probability 1, in SIAM Journal on Computing, vol. 10, n. 1, 1981, pp. 96–113, ISSN 1095-7111 (WC · ACNP).

[Babai-7] László Babai, Lance Fortnow, Noam Nisan, e Avi Wigderson (1993). "BPP has simulations in subexponential time unless EXPTIME has publishabke proofs". Computational Complexity, 3:307–318.

[8] Russell Impagliazzo and Avi Wigderson (1997). "P = BPP if E requires exponential circuits: Derandomizing the XOR Lemma". Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 220–229. DOI: 10.1145/258533.258590

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]