Editing BPP (complexity) (section)

{{Short description|Concept in computer science}}
<span lang="es" dir="ltr">In</span> [[computational complexity theory]], a branch of computer science, '''bounded-error probabilistic polynomial time''' ('''BPP''') is the class of [[decision problem]]s solvable by a [[probabilistic Turing machine]] in [[polynomial time]] with an error [[probability]] bounded by 1/3 for all instances.
'''BPP''' is one of the largest ''practical'' classes of problems, meaning most problems of interest in '''BPP''' have efficient [[probabilistic algorithm]]s that can be run quickly on real modern machines.  '''BPP''' also contains '''[[P (complexity)|P]]''', the class of problems solvable in polynomial time with a deterministic machine, since a deterministic machine is a special case of a probabilistic machine.

{| class="wikitable" style="float:right; clear:right; text-align:center; margin-left:1em;"
|-
!colspan="3"| BPP algorithm (1 run)
|-
! {{diagonal split header|Correct<br />answer|Answer<div style{{=}}"padding-left:4em;">produced</div>}}
! {{yes}}
! {{no}}
|-
! {{yes}}
| ≥ 2/3
| ≤ 1/3
|-
! {{no}}
| ≤ 1/3
| ≥ 2/3
|-
!colspan="3"| BPP algorithm (''k'' runs)
|-
! {{diagonal split header|Correct<br />answer|<div style{{=}}"padding-left:4em;">Answer</div>produced}}
! {{yes}}
! {{no}}
|-
! {{yes}}
| > 1 − 2<sup>−''ck''</sup>
| < 2<sup>−''ck''</sup>
|-
! {{no}}
| < 2<sup>−''ck''</sup>
| > 1 − 2<sup>−''ck''</sup>
|-
|colspan="3" style="font-size:85%"|for some constant ''c'' > 0
|}

Informally, a problem is in '''BPP''' if there is an algorithm for it that has the following properties:
*It is allowed to flip coins and make random decisions
*It is guaranteed to run in polynomial time
*On any given run of the algorithm, it has a probability of at most 1/3 of giving the wrong answer, whether the answer is YES or NO.