BPP (complessità)
Nella teoria della complessità computazionale, BPP (bounded-error probabilistic polynomial time, tempo polinomiale probabilistico con errore vincolato) è 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à di almeno 1/3 di dare la risposta sbagliata, 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 rafione è di grande interesse pratico quali problemi e classi di problemi siano all'interno di BPP. BPP contienen 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 dece essere nemmeno costante: la same classe di problemi è dedinita consentendo un errore elevato fino a 1/2 − n−c da un lato, o richiedendo un errore piccolo fino a 2−nc 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/2100, 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.
Note
Bibliografia
- Valentine Kabanets (2003). "CMPT 710 – Complexity Theory: Lecture 16". Simon Fraser University.
- Christos Papadimitriou, Computational Complexity, 1a 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".
