BPP (complessità): differenze tra le versioni

Versione delle 15:38, 8 mar 2014

Versione delle 15:39, 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