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

בעיות פתוחות במדעי המחשב: ${\mathsf {P}}{\overset {?}{=}}{\mathsf {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/2+1/poly$ היה נותן מחלקה זהה. הסיבה לכך, היא שניתן להעצים את הסתברות ההצלחה של האלגוריתם על ידי הרצתו מספר (פולינומי) של פעמים באופן בלתי תלוי ובחירת תוצאת הרוב. כך ניתן להקטין את סיכויי הכישלון באופן מעריכי עם מספר החזרות, כפי שניתן לנתח באמצעות אי-שוויון צ'רנוף.

יחס למחלקות אחרות

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

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

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

משפט סיפסר לאוטמן

משפט סיפסר לאוטמן קובע כי $BPP\subseteq \Sigma _{2}\cap \Pi _{2}$

אינטואיציה

המחלקה BPP היא המחלקה אשר מתירה טעות דו צדדית קטנה, כלומר טעות קטנה בתשובה "כן", וטעות קטנה בתשובה "לא". הכוונה בטעות קטנה היא שניתן בזמן פולינומי באורך הקלט להקטין אותה לטעות זניחה. מכיוון שיש מספר זניח של טעויות, אז "רוב" המחרוזות הראנדומיות הן מחרוזות שגורמות למכונה שמכריעה שפה ב-BPP להוציא תשובה נכונה (מחרוזות "נכונות"). לכן ניקח מספר פולינומי של פונקציות הפיכות שלאחר שנפעיל אותן על קבוצת המחרוזות הראנדומיות הנכונות נקבל את כל המחרוזות הרנדומיות הקיימות. מאחר שיש לנו קבוצת פונקציות כזאת, אז הנוסחה שתתאים ל$\Sigma _{2}$ היא $\exists F\ \forall r\ \bigvee _{i=1}^{|r|}M(f_{i}(r);x)=1$. כלומר לכל קלט ראנדומי קיימת פונקציה שממפה אותו לקלט מהקבוצה של הקלטים הנכונים. הפועל הפונקציות ההפיכות תהיינה פעולות xor עם ערך קבוע.

הוכחה

נרצה להוכיח עבור שפה $L\in BPP$ שמתקיים $L\in \Sigma _{2}$. מכיוון ש-BPP סגורה למשלים אז מתקיים גם $L\in \Pi _{2}$, ולכן $L\in \Sigma _{2}\implies L\in \Sigma _{2}\cap \Pi _{2}$. בלי הגבלת הכלליות ניקח מכונה הסתברותית M המכריעה את L עם הסתברות טעות לכל היותר $2^{-|x|}$. נגדיר $A(x)=\{r\ |\ M(r;x)=1\}$. עכשיו נמצא מספר קטן של פונקציות שיקיימו $\bigcup _{i=1}^{|F|}f_{i}(A(x))=R$, כאשר R הוא מרחב מרחב המחרוזות הרנדומיות (נגדיר הפעלה של פונקציה על קבוצה בתור הפעלה איבר איבר, כלומר $f(A)=\{f(a)\ |\ a\in A\}$). אנחנו נתייחס למרחב קלטים ראנדומי באורך r.

למה 1

נרצה להראות שקבוצה גדולה יכולה לכסות את כל R עם פונקציות מתאימות, או בשפה מתמטית

אם ${\frac {|A(x)|}{|R|}}\geq 1-2^{-|x|}$ אז קיימות מחרוזות תרגום $t_{1},t_{2},...,t_{n}$ כך ש$\bigcup _{i=1}^{n}A(x)\oplus t_{i}=R$. הפעולה $\oplus$ תוגדר כמו מקודם - $A\oplus t=\{a\oplus t\ |\ a\in A\}$.

הוכחה. נבחר באקראי $t_{1},t_{2},...,t_{|r|}$. נגדיר $S=\bigcup _{i}A(x)\oplus t_{i}$.

אז, לכל $r\in R$,

$\Pr {[r\notin S]}=\prod _{i=1}^{r}\Pr {[r\notin A(x)\oplus t_{i}]}\leq {\frac {1}{2^{|x|\cdot |r|}}}$.

לכן ההסתברות שקיים לפחות איבר אחד ב-R שאינו נמצא ב-S היא

$\Pr {\Bigl [}\bigvee _{i}r_{i}\notin S{\Bigr ]}\leq \sum _{i}{\frac {1}{2^{|x|\cdot |r|}}}={\frac {2^{|r|}}{2^{|x|\cdot |r|}}}<1$

ולכן

$\Pr[S=R]=1-{\frac {2^{|r|}}{2^{|x|\cdot |r|}}}>0$

ומכיוון שההסתברות לא 0 קיימות מחרוזות תרגום עבורן הקבוצות S ו-R שוות.

למה 2

נרצה להראות שקבוצה קטנה לא יכולה לכסות את כל R עם כל מספר פולינומי של פונקציות, או בשפה מתמטית אם ${\frac {|A(x)|}{|R|}}\leq 2^{-|x|}$ אז אין קבוצה קטנה של מחרוזות תרגום שמכסה את R.

ההוכחה טריוויאלית - ${\bigl |}\bigcup _{i}^{p(|x|)}A(x)\oplus t_{i}{\bigr |}\leq p(|x|){\frac {|A(x)|}{|R|}}$, ופולינום כפול מספר זניח הוא מספר זניח, ולכן לא קיים כיסוי עם אף סט קטן של מחרוזות תרגום.

מסקנה

ראינו שקיימות מחרוזות תרגום עבורן $\bigcup _{i}A(x)\oplus t_{i}=R$. לכן ניתן לכתוב

$\exists t_{1},t_{2},...,t_{|}r|\ \forall r\in R\bigvee _{1\leq i\leq |r|}M(x;r\oplus t_{i})=1$

ובגלל ההפיכות של xor, כלומר $a\oplus a={\bar {0}}$, אז אנחנו יודעים מלמה 1 שלכל r תהיה מחרוזת $t_{i}$ כך ש-$t_{i}\oplus r\in A(x)$, ולכן המכונה תקבל כל מילה בשפה. לעומת זאת, עבור מילים שאינן בשפה קיים r שאין עבורו שום תרגום ל-$A(x)$, ולכן ההגדרה שלמעלה תקינה. היא גם הגדרה מהצורה של $\Sigma _{2}$, ומכאן נובע ש-$L\in \Sigma _{2}\cap \Pi _{2}$, שהרי BPP סגורה למשלים.