פורטל:מדעי המחשב/הידעת?/12

BPP (ראשי תיבות של Bounded-Error, Probabilistic, Polynomial Time) הינה מחלקת הבעיות שיש עבורן אלגוריתם אקראי עם זמן ריצה פולינומי, אשר צודק בהסתברות "טובה": האלגוריתם יענה את התשובה הנכונה בהסתברות לפחות ε+½. המחלקה נחשבת כזו שמיצגת באופן הטוב ביותר את הבעיות שלהן יש אלגוריתם סביר.

המחלקה BPP מכילה את מחלקות הסיבוכיות RP ו-Co-RP, אשר מאפשרות טעות חד-צדדית בלבד, וכמובן את מחלקת הסיבוכיות P, אשר אינה מאפשרת אקראיות בכלל (ולכן, ממילא, האלגוריתם חייב לצדוק תמיד).