BPP (מחלקת סיבוכיות)

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

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

מקובל לראות בבעיות הנמצאות במחלקה זו בעיות "הניתנות לפתרון סביר".

הגדרה[עריכת קוד מקור | עריכה]

קיימות מספר הגדרות שקולות למחלקה זו, נציין אחת מהן.

מחלקת BPP מאגדת את כל השפות \ L להן קיים אלגוריתם אקראי A, הרץ בזמן פולינומי, ומקיים:

  1. לכל  x \in L, מתקיים A(x)=1 בהסתברות לפחות \frac{2}{3}.
  2. לכל  x \notin L, מתקיים A(x)=0 בהסתברות לפחות \frac{2}{3}.

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

יחס למחלקות אחרות[עריכת קוד מקור | עריכה]

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

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

לאור הידוע אודות "דה-רנדומיזציה", ההשערה המקובלת היא ש-BPP שווה למחלקה P‏[1].

הערות שוליים[עריכת קוד מקור | עריכה]