חישוב אקראי

אלגוריתמי מונטה קרלו ולאס וגאס, הגברת הצלחה ואלגוריתם הכיווץ של קרגר.

מטרות

• למדל מכונת טיורינג הסתברותית בעזרת סרט אקראיות.
• להבחין בין מונטה קרלו, לאס וגאס ושגיאה חד־צדדית, דו־צדדית ואפס.
• לנתח את בדיקת פרייבלדס, הגברה וכיווץ קרגר.
• למקם נכון את $\mathrm{RP}$, $\mathrm{coRP}$, $\mathrm{BPP}$ ו-$\mathrm{ZPP}$.

1. אקראיות אינה אי־דטרמיניזם

למכונת טיורינג הסתברותית (PTM) יש סרטי עבודה רגילים וגישה לביטים אקראיים הוגנים ובלתי־תלויים. אפשר לתאר כל מצב אקראי כשתי מעברים, כל אחד בהסתברות $1/2$. לאחר שקובעים מחרוזת אקראית $r$, החישוב דטרמיניסטי. אם המכונה קוראת $m(|x|)$ ביטים,

אי־דטרמיניזם שואל אם קיים ענף מקבל; אקראיות מודדת את החלק היחסי של מחרוזות האקראיות המקבלות. ענף מקבל נדיר מספיק ל-NP אך אינו מספיק להגדרת שגיאה חסומה.

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

2. מונטה קרלו ולאס וגאס

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

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

״נכון בתוחלת״ אינו לאס וגאס. ההגדרה היא: תמיד נכון, זמן אקראי.

3. בדיקת כפל המטריצות של פרייבלדס

בהינתן מטריצות $n\times n$ מעל שדה, $A,B,C$, הבדיקה אם $AB=C$ פועלת ב-$O(n^2)$ פעולות:

1. בוחרים $r\in\{0,1\}^n$ אחיד עם קואורדינטות בלתי־תלויות.
2. מחשבים $u=Br$, אחר כך $v=Au$ ו-$w=Cr$.
3. מקבלים אם ורק אם $v=w$.

אם $AB=C$, כל ריצה מקבלת. אחרת $D=AB-C\ne0$. בוחרים שורה לא־אפס ואינדקס $j$ שמקדמו אינו אפס. מתנים על כל קואורדינטות $r$ מלבד $r_j$. מבין שני ערכיו, לכל היותר אחד מאפס את המכפלה הסקלרית, כי שני הסכומים נבדלים במקדם הלא־אפס $D_{ij}$. לכן

זו שגיאת קבלה־שגויה חד־צדדית. דוגמה הדוקה מעל $\mathbb F_2$ היא

מתקיים $Dr=0$ בדיוק עבור $00,11$, כלומר בהסתברות $1/2$. אחרי $k$ וקטורים טריים, שוויון כוזב שורד בהסתברות לכל היותר $2^{-k}$.

4. הגברת הסתברות

אם כל ריצה בלתי־תלויה נכשלת בהסתברות לכל היותר $q<1$, והצלחה אחת מספיקה, אז כל $k$ הריצות נכשלות בהסתברות לכל היותר $q^k$. כדי להגיע ל-$\delta$ מספיק

בשגיאה חד־צדדית משלבים באמצעות OR או AND בכיוון ששומר על הצד המושלם. בשגיאת BPP דו־צדדית לוקחים רוב של מספר אי־זוגי של ריצות. מהצלחה של לפחות $2/3$, חסם צ'רנוף נותן שגיאה $\exp(-\Omega(k))$, ולכן $k=O(\log(1/\delta))$.

הגברה מקטינה שגיאה אך אינה מאפסת אותה ממש. שימוש חוזר באותה מחרוזת אקראית אינו חזרה בלתי־תלויה. הקבועים $1/2$ ו-$2/3$ מקובלים מפני שכל פער קבוע מ-$1/2$ ניתן להגברה.

5. מחלקות אקראיות

ל-PTM פולינומית $M$:

$\mathrm{ZPP}$ מכילה שפות בעלות אלגוריתם אפס־שגיאה בזמן פולינומי בתוחלת. מתקיים

להוכחת השוויון, מריצים לסירוגין מכונת RP ומכונת coRP עד שהראשונה מקבלת או השנייה דוחה. אף תשובת עצירה אינה שגויה, ובכל סיבוב יש הסתברות קבועה לעצירה. בכיוון השני קוטעים אלגוריתם אפס־שגיאה אחרי כפולה מתאימה של תוחלת זמנו. אי־שוויון מרקוב חוסם timeout; פירוש הפוך של timeout נותן RP ו-coRP.

לא ידוע אם $\mathrm{BPP}=\mathrm P$; אין להציג זאת כמשפט.

6. אלגוריתם הכיווץ של קרגר

בכל צעד בוחרים באופן אחיד צלע נוכחית ברב־גרף לא מכוון, מכווצים את קצותיה, מוחקים לולאות עצמיות ושומרים צלעות מקבילות. כשנותרים שני קודקודי־על, מחזירים את הצלעות שביניהם.

נקבע חתך מינימום $F$ בגודל $\lambda$. אם שרד עד שנותרו $i$ קודקודי־על, דרגת כל אחד לפחות $\lambda$; אחרת הצלעות היוצאות ממנו היו חתך קטן יותר. לכן יש לפחות $i\lambda/2$ צלעות ורק $\lambda$ מסוכנות. הסיכוי לכווץ את $F$ לכל היותר $2/i$, ולכן הסתברות הישרדותו לפחות

דוגמה פתורה

המכפלה המצטמצמת שווה $2/(n(n-1))$: הצלחה הפוכה־פולינומית, לא קבועה. אחרי $R$ ריצות בלתי־תלויות,

לכן $R=\Theta(n^2\log(1/\delta))$ מוריד כישלון ל-$\delta$. עבור $n=4$ החסם לחתך קבוע הוא $1/6$. במעגל $C_4$ יש כמה חתכי מינימום, ולכן מציאת חתך מינימום כלשהו יכולה להיות סבירה יותר. צלעות מקבילות נשמרות כי הריבוי שלהן הוא גם קיבולת החתך וגם משקל הדגימה.

7. השוואת ההבטחות

• פרייבלדס: זמן חסום $O(n^2)$ ושגיאה חד־צדדית; אחרי $k$ חזרות השגיאה לכל היותר $2^{-k}$.
• BPP: זמן פולינומי במקרה הגרוע ושגיאה דו־צדדית המרוחקת קבוע מ-$1/2$ לכל קלט.
• לאס וגאס/ZPP: אין תשובה שגויה, וזמן פולינומי בתוחלת.
• קרגר: כל פלט הוא חתך ישים, אך ריצה יחידה אופטימלית רק בהסתברות הפוכה־פולינומית.

אצל קרגר ״כישלון״ פירושו פתרון לא אופטימלי, לא פלט לא חוקי. ישימות ואיכות הן טענות נפרדות.

טעויות נפוצות

• לזהות ענפים אקראיים עם ענפים אי־דטרמיניסטיים.
• להגדיר נכונות רק בממוצע על קלטים.
• להניח אי־תלות כאשר הריצות משתמשות שוב באותם ביטים.
• לשלב חזרות חד־צדדיות בכיוון הלא נכון.
• לכנות ״נכון בתוחלת״ לאס וגאס.
• למחוק צלעות מקבילות בזמן כיווץ.
• לטעון שהגברה מאפסת שגיאה בדיוק.

המחשות

אפשר גם לצייר עץ חישוב PTM שעליו כל העלים שווי־משקל: NP דורשת עלה מקבל אחד, RP דורשת אפס בלא־מופעים והרבה בכן־מופעים, ו-BPP דורשת רוב חזק בכיוון הנכון.

תרגילים

תרגיל 1 — פרייבלדס כאשר $AB=C$

מה קורה באלגוריתם פרייבלדס כאשר $AB=C$? הוכיחו שאין דחייה שגויה במקרה זה.

תרגיל 2 — הגברה ל-$2^{-40}$

אלגוריתם בסגנון $\mathrm{RP}$ (במופעי־כן $\Pr[\text{קבלה}]\ge1/2$; במופעי־לא אין קבלה שגויה) מורץ $k$ פעמים בלתי־תלויות. מקבלים אם לפחות ריצה אחת מקבלת. כמה חזרות מורידות את הסתברות הדחייה השגויה במופע־כן ל-$\le2^{-40}$?

תרגיל 3 — ענף יחיד אינו RP

הוכיחו שענף מקבל יחיד של PTM אינו מוכיח שייכות ל-$\mathrm{RP}$.

תרגיל 4 — $\mathrm{ZPP}=\mathrm{RP}\cap\mathrm{coRP}$

הסבירו את שני כיווני $\mathrm{ZPP}=\mathrm{RP}\cap\mathrm{coRP}$.

תרגיל 5 — חסם קרגר על צלעות

מדוע בהוכחת קרגר חוסמים מלמטה את מספר הצלעות הנוכחי ב-$i\lambda/2$ כאשר נשארו $i$־על־קודקודים וחתך מינימלי $\lambda$?

8. ניתוחי הסתברות מפורטים

מדגימה מוטה לחישוב בביטים הוגנים

הגדרת PTM משתמשת בביטים הוגנים מטעמי נוחות, לא מפני שמותר לדגום רק קבוצות שגודלן חזקה של שתיים. כדי לדגום אחיד מתוך $\{1,\ldots,6\}$, קוראים שלושה ביטים כמספר בין $0$ ל-$7$; דוחים את $6,7$ ומנסים שוב. כל ערך מתקבל באותה הסתברות, והסיכוי לסיים סיבוב הוא $3/4$, ולכן מספר הסיבובים הצפוי $4/3$. זהו דוגם לאס וגאס קטן. עצירה קשיחה אחרי מספר ניסיונות הייתה מוסיפה אירוע כישלון והופכת אותו למונטה קרלו.

כשקרגר אומר ״בחר צלע אקראית״, הבחירה אחידה בין עותקי הצלעות הנוכחיים. בחירת שני קצוות אחידים הייתה התפלגות אחרת ומבטלת את החישוב. תרגום תיאור מילולי לפרוצדורת ביטים מדויקת הוא חלק מהגדרת האלגוריתם.

פרייבלדס מעל שלמים ושדות

מעל השלמים, אותו טיעון וקטור בינרי עובד משום שמקדם לא־אפס אינו נעלם כש-$r_j$ מתהפך. במימוש צריך לחשב עלות אריתמטית ולהימנע מ-overflow. אפשר לחשב מודולו ראשוני, אך אז מטריצת שגיאה שלמה לא־אפס עלולה להפוך לאפס מודולו הראשוני. אם הראשוני קבוע, זהו מקור שגיאה נוסף; אם בוחרים אותו אקראית מטווח מתאים, חייבים לנתח גם את ההסתברות הזאת. המשפט הנקי לעיל מניח פעולות שדה מדויקות ו-$AB\ne C$ באותו שדה.

פרייבלדס מאמת מכפלה נתונה; הוא אינו מחשב אותה. מכאן החיסכון: חישוב $Br$ ואז $A(Br)$ הוא שתי הכפלות מטריצה־וקטור, ואילו יצירת $AB$ מחשבת את כל מכפלות שורה־עמודה.

חשבון הגברה מדויק

נניח שריצת פרייבלדס עולה $2n^2+O(n)$ פעולות ושוויון כוזב עובר בהסתברות לכל היותר $1/2$. עשר ריצות עדיין עולות $O(n^2)$ כי עשר קבוע, ומורידות שגיאה ל-$1/1024$. כדי להגיע ל-$1/n^c$, בוחרים

והזמן נעשה $O(n^2\log n)$. כדי להגיע ל-$2^{-n}$ נדרשות $n$ ריצות וזמן $O(n^3)$, כך שהיתרון האסימפטוטי מול כפל יסודי נעלם. יעד השגיאה והזמן חייבים להיבדק יחד.

ב-BPP אסור להכפיל פשוט הסתברויות כישלון, מפני שרוב עלול להיות שגוי גם אם חלק מהריצות נכונות. נסמן ב-$Y_i$ נכונות; התוחלת של סכומן לפחות $2k/3$. שגיאת רוב דורשת ירידה מתחת $k/2$, סטייה לינארית שחסם צ'רנוף מוריד מעריכית. גם כאן אי־תלות חיונית.

המרת זמן צפוי בזהירות

לאלגוריתם אפס־שגיאה עם תוחלת זמן לכל היותר $p(n)$, מרקוב נותן

עוצרים אחרי $2p(n)$ צעדים. לגרסת RP מקבלים רק אם האלגוריתם עצר והשיב כן; אחרת דוחים. לא־מופע לעולם אינו מתקבל בטעות, וכן־מופע מתקבל בהסתברות לפחות $1/2$. לגרסת coRP מקבלים ב-timeout ושומרים את הצד המושלם ההפוך. אחר כך מגבירים.

חסם התוחלת צריך להיות אחיד וידוע במידה שמאפשרת לקבוע cutoff. זמני ריצה טובים בניסויים אינם הוכחת שייכות ל-ZPP.

קרגר: התניה בכל שלב

טיעון הדרגה של חתך המינימום הוא מותנה. אחרי כיווצים בטוחים, כל קודקוד־על מייצג קבוצה לא ריקה של קודקודים מקוריים. הצלעות היוצאות ממנו הן חתך בגרף המקורי, ולכן דרגתו לפחות $\lambda$. כך החסם נשאר נכון לאורך כל קידומת מצליחה.

כאשר נותרו $i$ קודקודים, הסתברות הישרדות הצעד הבא לפחות $(i-2)/i$. מותר להכפיל הסתברויות מותנות:

אירועי הכיווץ אינם בלתי־תלויים; הם תלויים מאוד. התניה היא הכלי הנכון. המכפלה מצטמצמת כי המונים $n-2,n-3,\ldots,1$ מבטלים כמעט את כל המכנים $n,n-1,\ldots,3$.

עקבת כיווץ קטנה

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

האלגוריתם אינו יודע את $\lambda$ או את החתך המוגן. הם קיימים רק בניתוח. זו תבנית נפוצה: מקבעים עד רצוי, מחשבים את הסיכוי שפעולות אקראיות ישמרו עליו, ואז חוזרים.

9. תבנית להוכחה אקראית

1. מגדירים סרט אקראיות או משתנים אקראיים מפורשים.
2. מציינים בדיוק אילו פלטים הם שגיאה.
3. מוכיחים זמן בנפרד מנכונות.
4. מתנים על ההיסטוריה כאשר הבחירות משנות את מרחב המדגם העתידי.
5. משתמשים באקראיות טרייה לפני הכפלת הסתברויות.
6. מציינים אם ההבטחה היא זמן מקרה־גרוע, זמן צפוי, איכות צפויה או נכונות בהסתברות גבוהה.
7. באופטימיזציה מוכיחים שכל פלט ישים גם בריצה לא מוצלחת.

כך נמנעת טעות קטגורית: יחס קירוב צפוי, מכריע בשגיאה חסומה, ואלגוריתם אפס־שגיאה בזמן צפוי הם שלוש הבטחות שונות אף שכולן משתמשות במטבעות.

בדיקות שפיות להגדרות המחלקות

מכונת RP רשאית לדחות כן־מופע, אך OR של חזרות שומר על כך שלא־מופע לעולם אינו מתקבל. מכונת coRP רשאית לקבל לא־מופע, ו-AND של חזרות שומר על צד הכן המושלם. עבור BPP, לא OR גולמי ולא AND גולמי מתאימים: כל אחד מקטין שגיאה אחת ומגדיל את האחרת. רוב מטפל בשני הצדדים באופן סימטרי.

חסם המחלקה הוא על מטבעות המכונה עבור כל קלט קבוע. הוא אינו מבטיח שקיים seed יחיד שטוב לכל הקלטים באורך מסוים. קיבוע seed טוב גלובלי הוא שאלת דה־רנדומיזציה ודורש טיעון נוסף. גם מחולל פסאודו־אקראי אינו יכול להחליף מטבעות אמיתיים בלי הוכחה שהוא מטעה את סוג החישוב הרלוונטי.

בעת דיווח אלגוריתם אקראי יש לכלול את פרמטר הביטחון $\delta$ בזמן הריצה. ״בהסתברות גבוהה״ פירושו המקובל כישלון לכל היותר $1/n^c$ עבור קבוע רצוי $c$. משגיאה קבועה זה עולה בדרך כלל $O(\log n)$ חזרות; מקרגר, שהצלחתו בריצה יחידה הפוכה־פולינומית, נדרשות $O(n^2\log n)$ ריצות.

דוגמת סיווג

אלגוריתם שבקלט כן מחזיר כן בהסתברות $0.9$, ובקלט לא לעולם אינו מחזיר כן, הוא RP לאחר התאמת הקבוע. אלגוריתם שעוצר תמיד, נכון בהסתברות $0.9$ בשני סוגי הקלט, הוא BPP. אלגוריתם שתמיד נכון אך תוחלת זמנו $n^3$ הוא ZPP. ואם הוא תמיד נכון אך רק החציון הניסויי של זמנו פולינומי, עדיין לא הוכחה שייכות ל-ZPP.

תוחלת אינה הסתברות גבוהה

מהעובדה שערך חתך צפוי הוא $|E|/2$ לא נובע שהערך לפחות $|E|/2$ בהסתברות גבוהה. ייתכן פיזור רחב. כדי לקבל טענת הסתברות יש להפעיל חסם ריכוז מתאים או לחזור ולבחור את הטוב ביותר, תוך ניתוח מפורש. לעומת זאת, תוחלת כן מוכיחה שקיים לפחות פלט אחד שערכו לפחות התוחלת; אחרת כל הערכים היו קטנים ממנה.

בחירת אלגוריתם לפי סוג ההבטחה

אם יש מאמת דטרמיניסטי מהיר לתשובה מוצעת, אפשר לעיתים להפוך הליך שמוצא הצעה בהסתברות קבועה ללאס וגאס: דוחים הצעה שלא עברה אימות ומנסים שוב. אם אי־אפשר לזהות תשובה שגויה, חזרה לבדה אינה נותנת אפס שגיאה; משתמשים בהגברה מתאימה. בפרייבלדס, למשל, קבלה אינה מוכיחה שהמכפלה נכונה, ולכן אי־אפשר פשוט ״לחזור עד קבלה״ ולטעון לאס וגאס.

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

סיכום

אקראיות אינה אי־דטרמיניזם: נדרשים הסתברויות, צדדיות שגיאה והגברה. המחלקות RP, coRP, BPP ו-ZPP מקבעות הבטחות שונות.

תרגול מודרך

משימה 1 — Monte Carlo מול Las Vegas

הבחינו בין Monte Carlo ל-Las Vegas בזמן, שגיאה ודוגמה (פרייבלדס מול דגימה עם דחייה).

משימה 2 — RP מול NP

כתבו את הכמתים/ההסתברויות ל-$\mathrm{NP}$ ול-$\mathrm{RP}$ על כן־מופע ולא־מופע.

משימה 3 — תבנית הוכחה אקראית

סכמו תבנית בת חמישה שלבים להוכחת אלגוריתם אקראי (כפי שנלמד ביחידה).

נתיב מקורות וסמכות

• ראיות מן הסיכום הסטודנטיאלי (היקף בלבד): סיכומי שיעור/סיכום ממוזג.pdf, עמ׳ 86–94, 96 ו-136–139 (הטיפול של הסיכום בחישוב אקראי). אלגוריתם הכיווץ של קרגר אינו מופיע בסיכום הממוזג, ולכן האלגוריתם והניתוח לעיל הם העשרה הנתמכת בספרי הלימוד בלבד. הסיכום קובע דגש קורסי, לא סמכות לקבועים או לשוויוני מחלקות.
• סמכות ספרי לימוד: Arora–Barak, Computational Complexity: A Modern Approach, טיוטת 2007, פרק 7, §§7.1–7.4, עמ׳ ספר 115–124; Papadimitriou, Computational Complexity, פרק 11, §§11.1–11.3, עמ׳ 241–267; Sipser, מהדורה 3, §10.2, עמ׳ 396–408.
• מצב עריכתי: הגדרות המחלקות, חסם פרייבלדס, ההגברה ומכפלת הכיווץ נבדקו מול המסגרות האלה והגזירות הסטנדרטיות. נבדק; ביטחון גבוה.