מפת הסיבוכיות
EN
תרגיל

הגברת אלגוריתמים אקראיים חד־ודו־צדדיים

בחירת מספר חזרות וכללי צבירה וגזירת חסמי שגיאה מפורשים.

מקורות מטלות

הכנה איכותית למבחן ופתרונות קהילתיים — נוי 2025פתרון קהילתיפתרון מטלה 5 - סיבוכיות.pdfAssignment 5הכנה איכותית ופתרון קהילתי — אינו מקור רשמי

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

q-6559842decc0בהרצאה הוצג אלגוריתם הסתברותי לבעיית וידוא כפל מטריצות. נציע להלן שני אלגוריתמים נוספים לבעיה זו. עבור איזה ערך של m שני האלגוריתמים מבטיחים את אותו ח…0 בחינות · 1 מטלות · שיעורים 12, 13, 14

שאלה

אלגוריתם RP מקבל מופע כן בהסתברות לפחות 1/21/2 ולעולם אינו מקבל מופע לא. אלגוריתם BPP צודק בהסתברות לפחות 2/32/3. עבור הרצות בלתי־תלויות, תכננו הגברה לשגיאה לכל היותר δ\delta, הוכיחו חסמים והסבירו את חשיבות האקראיות הטרייה וכלל הצבירה.

דרישות קדם

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

רמז 1

ב-RP קבלו אם הרצה כלשהי מקבלת.

רמז 2

ב-BPP השתמשו במספר אי־זוגי וברוב.

רמז 3

הפעילו חסם צ'רנוף או הופדינג על משתנים בלתי־תלויים.

בנייה מודרכת

הגברת ההצלחה של אלגוריתמים אקראיים

שלב 1 מתוך 6
הגברת שגיאה באלגוריתמים אקראיים על פני הרצות בלתי תלויותרצועת הרצות בלתי תלויות מזינה שער OR עבור RP ושער רוב עבור BPP, ומעליהם גרף בסקאלה לוגריתמית המשווה את שגיאת RP שהיא שתיים בחזקת מינוס k, את שגיאת הרוב המדויקת של BPP, את תקרת הופדינג e בחזקת מינוס k חלקי שמונה־עשרה, וקו ישר המתאר שימוש חוזר באותה מחרוזת אקראית.הרצות בלתי תלויות (המחשה קבועה)RP · OR✗BPP · רוב✓הסתברות השגיאה כפונקציה של מספר ההרצות110⁻¹10⁻²10⁻³10⁻⁴10⁻⁵10⁻⁶10⁻⁷159131721k הרצות בלתי תלויותהסתברות שגיאה (סקאלה לוגריתמית)
✓ ההרצה מקבלת מופע כן · ההרצה עונה נכון✗ ההרצה מפספסת מופע כן · ההרצה עונה שגוי
הרצה אחת מכל סוגRP: Pr[accept | yes] ≥ 1/2, Pr[accept | no] = 0BPP: Pr[correct] ≥ 2/3 על כל קלטכל תוצאה מוצגת היא המחשה קבועה, ולכן התמונה זהה אצל כל הקוראים.

פתרון מלא

ב-RP מריצים rr פעמים עם ביטים בלתי־תלויים ומקבלים אם הרצה כלשהי קיבלה. מופע לא עדיין לעולם אינו מתקבל. במופע כן הסתברות שכל ההרצות ייכשלו היא לכל היותר 2−r2^{-r}, ולכן די ב-

r=⌈log⁡2(1/δ)⌉.r=\lceil\log_2(1/\delta)\rceil.

ב-BPP בוחרים rr אי־זוגי ומכריעים לפי רוב. יהי XiX_i משתנה המציין שהרצה ii נכונה. אז EXi≥2/3\mathbb EX_i\ge2/3, ושגיאה דורשת לכל היותר r/2r/2 הצלחות. לפי הופדינג,

Pr⁡[רוב שגוי]≤e−r/18.\Pr[\text{רוב שגוי}]\le e^{-r/18}.

לכן די ב-r≥18ln⁡(1/δ)r\ge18\ln(1/\delta), מעוגל למספר אי־זוגי. קבועים חדים יותר אינם משנים את O(log⁡(1/δ))O(\log(1/\delta)).

הזמן מוכפל ב-rr. שגיאה n−cn^{-c} דורשת O(log⁡n)O(\log n) הרצות, ושגיאה 2−nc2^{-n^c} דורשת O(nc)O(n^c), ולכן נשמר זמן פולינומי.

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

נקודות בדיקה

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

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

  • כפל הסתברויות בלי עצמאות.
  • שימוש ב-OR לשגיאה דו־צדדית.
  • הגברת הצלחה בדיוק 1/21/2 בעזרת רוב.

מקורות ואימות

  • Merged summary, pp. 89-94 and p. 96
  • Arora-Barak draft, sec. 7.1
  • Papadimitriou, ch. 11
  • מיפוי קטלוג: data/exercises.json; הניסוח והפתרון עצמאיים; הגשות אישיות אינן מקור סמכות.

הערת מקור וביטחון

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

פתיחה בגלריית ההמחשות: הגברת ההצלחה של אלגוריתמים אקראיים