BPP (complessità): differenze tra le versioni

Versione delle 17:28, 8 mar 2014

Versione delle 18:11, 8 mar 2014

Riga 62:

* 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''' ?}}

Besides the problems in '''P''', which are obviously in '''BPP''', many problems were known to be in '''BPP''' but not known to be in '''P'''. The number of such problems is decreasing, and it is conjectured that '''P''' = '''BPP'''.

== ProblemsProblemi ==

For a long time, one of the most famous problems that was known to be in '''BPP''' but not known to be in '''P''' was the problem of [[primality test|determining]] whether a given number is [[prime number|prime]]. However, in the 2002 paper ''[[AKS primality test|PRIMES is in '''P''']]'', [[Manindra Agrawal]] and his students [[Neeraj Kayal]] and [[Nitin Saxena]] found a deterministic polynomial-time algorithm for this problem, thus showing that it is in '''P'''.

{| class=wikitable style="float:right; width:30%; margin:0em 1em 1em 1em;"

|+ Lista di problemi irrisolti in [[informatica]]

|-

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

|}

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 in '''P''' era il problema di determinare se un numero dato è [[Numero primo|primo]]. Tuttavia, nel saggio del 2002 ''[[Algoritmo AKS|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'''.

An important example of a problem in '''BPP''' (in fact in '''[[RP (complexity)|co-RP]]''') still not known to be in '''P''' is [[polynomial identity testing]], the problem of determining whether a polynomial is identically equal to the zero polynomial. In other words, is there an assignment of variables such that when the polynomial is evaluated the result is nonzero? It suffices to choose each variable's value uniformly at random from a finite subset of at least ''d'' values to achieve bounded error probability, where ''d'' is the total degree of the polynomial.<ref>Madhu Sudan and Shien Jin Ong. Massachusetts Institute of Technology: 6.841/18.405J Advanced Complexity Theory: [http://people.csail.mit.edu/madhu/ST03/scribe/lect06.pdf Lecture 6: Randomized Algorithms, Properties of BPP]. February 26, 2003.</ref>

Un esempio importante di un problema in '''BPP''' (in realtà in '''[[RP (complessità)|co-RP]]''') che ancora non si conosce in '''P''' è la [[verifica dell'identità dei polinomi]], il problema di determinare se unpolinomio è 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.<ref>Madhu Sudan e Shien Jin Ong, ''Advanced Complexity Theory: [http://people.csail.mit.edu/madhu/ST03/scribe/lect06.pdf Lecture 6: Randomized Algorithms, Properties of BPP''], Massachusetts Institute of Technology: 6.841/18.405J, 26 febbraio 2003.</ref>

<!--

== Related classes ==

If the access to randomness is removed from the definition of '''BPP''', we get the complexity class '''P'''. In the definition of the class, if we replace the ordinary [[Turing machine]] with a [[quantum computer]], we get the class '''[[BQP]]'''.