BPP

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

הגדרת המחלקה באמצעות הקבוע 2/3 הינה שרירותית, שכן באמצעות חזרה על האלגוריתם מספר רב של פעמים ובחירת התשובה השכיחה יותר (טכניקה הידועה כ-הגברה (amplification)), ניתן להוריד את הסתברות הטעות לקטנה ככל שרוצים.

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

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