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

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

מחלקת BPP כוללת את כל השפות L שיש להן מכונת רנדום A שעובדת בזמן פולינומי ומקיימת: אם x שייך ל‑L אז A עונה "כן" בהסתברות ≥2/3, ואם x לא שייך ל‑L אז A עונה "לא" בהסתברות ≥2/3. המספר 2/3 הוא שרירותי: ניתן להקטין את סיכוי הטעות על ידי הרצת האלגוריתם מספר פולינומי פעמים ובחירת הרוב (העצמת ההצלחה), ניתוח שנעשה בעזרת אי‑שוויון צ'רנוף, כלי שמראה שסיכויי הכישלון יורדים בצורה מעריכית בהרצות רבות.

BPP כוללת את RP, co‑RP ואת P (שבה אין אקראיות). ידוע ש‑BPP כלולה ב‑PP וב‑P/Poly, אך לא ידוע אם BPP שווה ל‑P או מה יחס BPP ל‑NP. ההשערה המקובלת היא ש־BPP = P (דה‑רנדומיזציה).

קיים תוצא מוכח: BPP ⊆ Σ2 ∩ Π2. כלומר כל שפה ב‑BPP מתוארת על ידי נוסחאות בשכבה השנייה של פירמידת הפולינום.

אלגוריתם ב‑BPP טועה רק לעיתים נדירות. זאת אומרת, רוב רצפי הביטים שאלגוריתם אקראי משתמש בהם מגוונים ומובילים לתשובה נכונה. בעזרת קבוצת פונקציות הפיכות פשוטות (למשל פעולות XOR עם וקטור קבוע), אפשר למפות את רוב הרצפים הנכונים על פני כל מרחב הרצפים, וכך לבנות נוסחה במבנה Σ2 שמבטאת את ההכרעה.

=הוכחה (ברעיון)
מגדירים A(x) כאוסף רצפי ההגרלות שהמכונה מקבלת עליהם את x. אם A(x) הוא "גדול" מספיק, בוחרים אקראית כמה וקטורי תרגום t_i (פעולת XOR עם t_i) ומראים שבעקבות ההטלות הללו קבוצת התמונות מכסה את כל מרחב ההגרלות. הסתברות הכיסוי חיובית, לכן קיימים t_i מתאימים. אם A(x) קטן מאוד, שום קבוצה פולינומית של תרגומים לא תכסה את המרחב. מהשילוב מקבלים נוסחה של הצורה "קיימים תרגומים כך שלכל ראנדום לפחות אחד מהם מוביל לקבלה", שהיא נוסחה ב‑Σ2. מכיוון שב‑BPP אפשר להשלים את התשובה, גם הסתירה נכנסת ל‑Π2, ומכאן BPP ⊆ Σ2 ∩ Π2.

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

BPP היא קבוצה של בעיות שמחשב יכול לפתור בעזרת ריצות שרצות בהגרלה. אלגוריתם אקראי (אלגוריתם שמשתמש בהגרלות) עונה נכון בדרך כלל.

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

BPP מכילה את P (בעיות שנפתרות בלי אקראיות), וגם מכילה תתי‑מחלקות כמו RP ו‑co‑RP. לא יודעים אם BPP זהה ל‑P או מה הקשר ל‑NP.

יש משפט שאומר ש‑BPP נמצאת במקום מיוחד במבנה של מחלקות הקושי, שנקרא Σ2 ו‑Π2.

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

BPP הן בעיות שמחשב יכול לפתור מהר עם קצת מזל. אפשר לחזק את ההצלחה על ידי חזרות. יש הוכחות שמראות היכן BPP נמצאת במפה של מחלקות סיבוכיות.