|
Nella [[teoria della complessità computazionale]], '''BPP''' (''boundedBounded-error probabilisticProbabilistic polynomialPolynomial time'', "tempo polinomiale probabilistico con errore vincolatolimitato") è una [[classe di complessità]] a cui appartengono quei [[Problema decisionale|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.
{| class="wikitable" style="float:right; text-align:center; margin: 1em 0 1em 1em;"
|}
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à dial almenopiù 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 [[Algoritmo probabilistico|algoritmi probabilistici]] efficienti che possono essere eseguiti su macchine moderne reali. Per questa rafioneragione è di grande interesse pratico quali problemi e classi di problemi siano all'interno di '''BPP'''. '''BPP''' contienencontiene anche '''[[P''' (complessità)|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 matematica|costante]] fra 0 e 1/2 (esclusiva) e l'insieme '''BPP''' sarà immutato. Non decedeve nemmeno essere nemmeno costante: la samestessa classe di problemi è dedinitadefinita consentendo un errore elevato fino a 1/2 − ''n''<sup>−''c''</sup> da un lato, o richiedendo un errore piccolo fino a 2<sup>−''n<sup>c</sup>''</sup> 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<sup>100</sup>, 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
{{unsolved|computer science|Is '''P''' {{=}} '''BPP''' ?}}
▲* 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
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'''.
* 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.
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'''.
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 è [[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 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.<ref>Madhu Sudan e Shien Jin Ong, ''Advanced Complexity Theory: [https://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]]'''.
== Classi correlate ==
Adding [[postselection]] to '''BPP''', or allowing computation paths to have different lengths, gives the class '''BPP'''<sub>path</sub>.<ref>[http://qwiki.stanford.edu/index.php/Complexity_Zoo:B#bpppath]</ref> '''BPP'''<sub>path</sub> is known to contain '''NP''', and it is contained in its quantum counterpart '''[[PostBQP]]'''.
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 (complessità)|BQP]].
Aggiungere la [[postselezione]] a BPP, o consentire ai percorsi di computazione di avere lunghezze diverse, dà la classe BPP<sub>path</sub>.<ref>[http://qwiki.stanford.edu/index.php/Complexity_Zoo:B#bpppath] {{webarchive|url=https://web.archive.org/web/20120805060809/http://qwiki.stanford.edu/index.php/Complexity_Zoo:B|data=5 agosto 2012}}</ref> È noto che BPP<sub>path</sub> contiene [[NP (complessità)|NP]], ed è contenuto nella sua controparte quantistica [[PostBQP]].
A [[Monte Carlo algorithm]] is a [[randomized algorithm]] which is likely to be correct. Problems in the class '''BPP''' have Monte Carlo algorithms with polynomial bounded running time. This is compared to a [[Las Vegas algorithm]] which is a randomized algorithm which either outputs the correct answer, or outputs "fail" with low probability. Las Vegas algorithms with polynomial bound running times are used to define the class '''[[ZPP (complexity)|ZPP]]'''. Alternatively, '''ZPP''' contains probabilistic algorithms that are always correct and have expected polynomial running time. This is weaker than saying it is a polynomial time algorithm, since it may run for super-polynomial time, but with very low probability.
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 (complessità)|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.
== Complexity-theoretic properties ==
[[File:Randomized Complexity Classes.svg|thumb|BPP in relation to other probabilistic complexity classes]] ▼
== Proprietà della teoria della complessità ==
It is known that '''BPP''' is closed under [[Complement (complexity)|complement]]; that is, '''BPP''' = '''co-BPP'''. '''BPP''' is [[low (complexity)|low]] for itself, meaning that a '''BPP''' machine with the power to solve '''BPP''' problems instantly (a '''BPP''' [[oracle machine]]) is not any more powerful than the machine without this extra power. In symbols, '''BPP'''<sup>'''BPP'''</sup> = '''BPP'''.
▲[[File:Randomized Complexity Classes.svg|thumb|BPP in relationrelazione toad otheraltre probabilisticclassi complexitydi classescomplessità probabilistica]]
Si sa che BPP è chiuso sotto il [[Complemento (complessità)|complemento]]; cioè, BPP = co-BPP. BPP è [[Basso (complessità)|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<sup>BPP</sup> = BPP.
The relationship between '''BPP''' and '''[[NP (complexity)|NP]]''' is unknown: it is not known if '''BPP''' is a [[subset]] of '''[[NP (complexity)|NP]]''', '''NP''' is a subset of '''BPP''' or if they are incomparable. If '''NP''' is contained in '''BPP''', which is considered unlikely since it would imply practical solutions for [[NP-complete]] problems, then '''NP''' = '''RP''' and '''[[PH (complexity)|PH]]''' ⊆ '''BPP'''.<ref>[http://weblog.fortnow.com/2005/12/pulling-out-quantumness.html]</ref>
La relazione tra BPP e [[NP (complessità)|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-completo|NP-completi]], allora NP = RP e [[PH (complessità)|PH]] ⊆ BPP.<ref>{{Cita web |url=http://weblog.fortnow.com/2005/12/pulling-out-quantumness.html |titolo=Computational Complexity: Pulling Out The Quantumness<!-- Titolo generato automaticamente --> |accesso=6 marzo 2014 |urlarchivio=https://web.archive.org/web/20060314023701/http://weblog.fortnow.com/2005/12/pulling-out-quantumness.html |dataarchivio=14 marzo 2006 |urlmorto=sì }}</ref>
It is known that '''[[RP (complexity)|RP]]''' is a subset of '''BPP''', and '''BPP''' is a subset of '''[[PP (complexity)|PP]]'''. It is not known whether those two are strict subsets, since we don't even know if '''P''' is a strict subset of '''PSPACE'''. '''BPP''' is contained in the second level of the [[polynomial hierarchy]] and therefore it is contained in '''PH'''. More precisely, the [[Sipser–Lautemann theorem]] states that <math>\ BPP \subseteq \Sigma_2 \cap \Pi_2 </math>. As a result, '''P''' = '''NP''' leads to '''P''' = '''BPP''' since '''PH''' collapses to '''P''' in this case. Thus either '''P''' = '''BPP''' or '''P''' ≠ '''NP''' or both.
È noto che [[RP (complessità)|RP]] è un sottoinsieme di BPP, e BPP è un sottoinsieme di [[PP (complessità)|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 <math>\ BPP \subseteq \Sigma_2 \cap \Pi_2 </math>. 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.
[[Adleman's theorem]] states that membership in any language in '''BPP''' can be determined by a family of polynomial-size [[Boolean circuit]]s, which means '''BPP''' is contained in '''[[P/poly]]'''.<ref>{{cite conference | author = [[Leonard Adleman|Adleman, L. M.]] | title = Two theorems on random polynomial time | booktitle = Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computing | year = 1978 | pages = 75–83}}</ref> Indeed, as a consequence of the proof of this fact, every '''BPP''' algorithm operating on inputs of bounded length can be derandomized into a deterministic algorithm using a fixed string of random bits. Finding this string may be expensive, however.
Il [[teorema di Adleman]] afferma che l'appartenenza in qualsiasi linguaggio in BPP può essere determinata da una famiglia di [[Circuito booleano|circuiti booleani]] di dimensione polinomiale, che significa che BPP è contenuto in [[P/poly]].<ref>{{cita conferenza | autore = [[Leonard Adleman|Adleman, L. M.]] | titolo = Two theorems on random polynomial time | conferenza = Proceedings of the Nineteenth Annual IEEE Symposium on Foundations of Computing | anno = 1978 | pagine = 75–83}}</ref> 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.
Relative to oracles, we know that there exist oracles A and B, such that '''P'''<sup>A</sup> = '''BPP'''<sup>A</sup> and '''P'''<sup>B</sup> ≠ '''BPP'''<sup>B</sup>. Moreover, relative to a [[random oracle]] with probability 1, '''P''' = '''BPP''' and '''BPP''' is strictly contained in '''NP''' and '''co-NP'''.<ref>{{Citation | last1=Bennett | first1=Charles H. | author1-link=Charles H. Bennett (computer scientist) | last2=Gill | first2=John | title=Relative to a Random Oracle A, P^A != NP^A != co-NP^A with Probability 1 | year=1981 | journal=SIAM Journal on Computing | issn=1095-7111 | volume=10 | issue=1 | pages=96–113}}</ref> ▼
▲RelativeRelativamente toagli oraclesoracoli, wesappiamo knowche thatesistono there exist oraclesoracoli A ande B, suchtali thatche '''P '''<sup>A</sup> = '''BPP '''<sup>A</sup> ande '''P '''<sup>B</sup> ≠ '''BPP '''<sup>B</sup>. MoreoverInoltre, relative to arelativamente all'[[ Oracolo random |oracolo oraclecasuale]] withcon probabilityprobabilità 1, '''P ''' = '''BPP ''' ande '''BPP ''' isè strictlystrettamente containedcontenuto in '''NP ''' ande '''co-NP '''.<ref>{{ CitationCita testo | last1cognome1=Bennett | first1nome1=Charles H. | author1-linkwkautore1=Charles H. Bennett (computer scientist) | last2cognome2=Gill | first2nome2=John | titletitolo=Relative to a Random Oracle A, P^A != NP^A != co-NP^A with Probability 1 | yearanno=1981 | journalrivista=SIAM Journal on Computing | issn=1095-7111 | volume=10 | issuenumero=1 | pagespp= 96–11396-113}}</ref>
== Derandomization ==
The existence of certain strong [[pseudorandom number generators]] is [[conjecture]]d by most experts of the field. This conjecture implies that randomness does not give additional computational power to polynomial time computation, that is, '''P''' = '''RP''' = '''BPP'''. Note that ordinary generators are not sufficient to show this result; any probabilistic algorithm implemented using a typical random number generator will always produce incorrect results on certain inputs irrespective of the seed (though these inputs might be rare).
== Derandomizzazione ==
[[László Babai]], [[Lance Fortnow]], [[Noam Nisan]], and [[Avi Wigderson]] showed that unless '''[[EXPTIME]]''' collapses to '''[[MA (complexity)|MA]]''', '''BPP''' is contained in<ref name="Babai">László Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson (1993). "'''BPP''' has subexponential time simulations unless '''EXPTIME''' has publishable proofs". ''Computational Complexity'', 3:307–318.</ref> ▼L'esistenza di certi [[Numeri pseudocasuali|generatori forti di numeri casuali]] è [[congettura]]ta 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]], ande [[Avi Wigderson]] showeddimostrarono thatche unlessa meno che '''[[EXPTIME]] ''' collapsescollassi toa '''[[MA ( complexitycomplessità)|MA]] ''', '''BPP ''' isè containedcontenuto in<ref name="Babai">László Babai, Lance Fortnow, Noam Nisan, ande Avi Wigderson (1993). " '''BPP ''' has simulations in subexponential time simulations unless '''EXPTIME ''' has publishablepublishabke proofs". ''Computational Complexity'', 3:307–318.</ref>
:<math>\mathbf{i.o.-SUBEXP} = \bigcap\nolimits_{\varepsilon>0} \mathbf{i.o.-DTIME} \left (2^{n^\varepsilon} \right).</math>
TheLa classclasse '''i.o.-SUBEXP''', whichche standssta forper ''infinitely often '''SUBEXP''', containsossia problemsinfinitamente spesso SUBEXP, whichcontiene haveproblemi che hanno algoritmi in [[sub-exponentialtempo timesubesponenziale]] algorithmsper forinfinitamente infinitelymolte manydimensioni dell'input sizes. TheyEssi alsomostrarono showedanche thatche '''P''' = '''BPP''' ifse thela exponential-timegerarchia hierarchydel tempo esponenziale, whichche isè defineddefinita in terms oftermini thedella [[polynomialgerarchia hierarchypolinomiale]], ande che '''E''' ascome '''E<sup>PH</sup>''', collapsescollassa toa '''E'''; howevertuttavia, notesi thatnoti theche exponential-timesi hierarchycongettura ische usuallyla conjecturedgerarchia del tempo esponenziale di solito ''notnon'' to collapsecollassi.
[[Russell Impagliazzo]] ande Avi Wigderson showeddimostrarono thatche ifse anyun problemqualsiasi problema in '''[[E (complexitycomplessità)|E]]''', wheredove
:<math>\mathbf{E} = \mathbf{DTIME} \left( 2^{O(n)} \right),</math>
hasha circuit[[complessità complexitydei circuiti]] 2<sup>Ω(''n'')</sup> thenallora '''P''' = '''BPP'''.<ref>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}}</ref>
-->
==Note==
<references />
==Bibliografia==
* <span id="Kabanets">Valentine Kabanets (2003). "CMPT 710 – Complexity Theory: Lecture 16". [[Simon Fraser University]].</span>
* {{cita libro|autore = [[Christos Papadimitriou]] | anno = 1993 | titolo = Computational Complexity | editore= Addison Wesley | edizione = 1<sup>a</sup>ª edizione | isbn = 0-201-53082-1}} pp. 257–259 della sezione 11.3: "Random Sources". pp. 269–271 della sezione 11.4: "Circuit complexity".
* {{cita libro|autore = [[Michael Sipser]] | anno = 1997 | titolo = Introduction to the Theory of Computation |url = https://archive.org/details/introductiontoth00sips | editore = PWS Publishing | isbn = 0-534-94728-X}} Sezione 10.2.1: "The class BPP, pp. 336–339".
==Collegamenti esterni==
* {{en}}cita [httpweb|https://www.cs.princeton.edu/courses/archive/fall03/cs597E/ |Princeton CS 597E: Derandomization paper list]|lingua=en}}
* {{en}}[cita web|1=http://www.courses.fas.harvard.edu/~cs225/ |2=Harvard CS 225: Pseudorandomness]|lingua=en|accesso=6 marzo 2014|urlarchivio=https://web.archive.org/web/20030805021413/http://www.courses.fas.harvard.edu/~cs225/|dataarchivio=5 agosto 2003|urlmorto=sì}}
{{Classi di complessità}}
{{Portale|informatica|matematica}}
[[Categoria:Classi di complessità probabilistiche]]
{{Portale|Matematica|Informatica}}
[[Categoria:Complessità computazionale]]
[[Categoria:Matematica per l'informatica]]
| 