BPP (complessità): differenze tra le versioni

Versione delle 15:39, 8 mar 2014

Versione delle 17:28, 8 mar 2014

Riga 49:

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 matematica|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^{−''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 [[Decadimento esponenziale|cala esponenzialmente]] come conseguenza del [[vincolo di Chernoff]].<ref>[http://www.cs.sfu.ca/~kabanets/cmpt710/lec16.pdf]</ref> 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.

<!--

== Definition ==

A language ''L'' is in '''BPP''' if and only if there exists a probabilistic Turing machine ''M'', such that

* ''M'' runs for polynomial time on all inputs

* For all ''x'' in ''L'', ''M'' outputs 1 with probability greater than or equal to 2/3

* For all ''x'' not in ''L'', ''M'' outputs 1 with probability less than or equal to 1/3

Unlike the complexity class '''[[ZPP (complexity)|ZPP]]''', the machine ''M'' is required to run for polynomial time on all inputs, regardless of the outcome of the random coin flips.

== Definizione ==

Alternatively, '''BPP''' can be defined using only deterministic Turing machines. A language ''L'' is in '''BPP''' if and only if there exists a polynomial ''p'' and deterministic Turing machine ''M'', such that

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

* ''M'' runs for polynomial time on all inputs

* ''M'' funziona per un tempo polinomiale su tutte le immissioni

* For all ''x'' in ''L'', the fraction of strings ''y'' of length ''p''(|''x''|) which satisfy ''M(x,y)'' = 1 is greater than or equal to 2/3

* ForPer alltutti gli ''x'' not in ''L'', the fraction of strings ''y'' of length ''p''(|''x''|) which satisfy ''M(x,y)'' =emette 1 iscon lessprobabilità thanmaggiore oro equaluguale toa 12/3

* Per tutti gli ''x'' non in ''L'', ''M'' emette 1 con probabilità minore o uguale a 1/3

In this definition, the string ''y'' corresponds to the output of the random coin flips that the probabilistic Turing machine would have made. For some applications this definition is preferable since it does not mention probabilistic Turing machines.

Diversamente dalla classe di complessità '''[[ZPP (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

* ForPer alltutti gli ''x'' in ''L'', thela fractionfrazione ofdi stringsstringhe ''y'' ofdi lengthlunghezza ''p''(|''x''|) whichche satisfysoddisfano ''M(x,y)'' = 1 is greaterè thanmaggiore oro equaluguale toa 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.

<!--

== Problems ==

{{unsolved|computer science|Is '''P''' {{=}} '''BPP''' ?}}