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

פירוש מחסומי יחסיות בעזרת אורקלים

עבודה עם מחלקות אורקל והסקת המגבלה המדויקת מעולמות אורקל מנוגדים.

שאלה

מכונת אורקל שואלת בשלב אחד אם מחרוזת שייכת ל-AA; הגדירו PA,NPAP^A,NP^A. נניח שקיימים אורקלים A,BA,B שעבורם PA=NPAP^A=NP^A אך PB≠NPBP^B\ne NP^B. הסבירו מה נובע לגבי הוכחות יחסיות ומה לא נובע לגבי PP מול NPNP. הוכיחו גם PA⊆NPA⊆PSPACEAP^A\subseteq NP^A\subseteq PSPACE^A.

דרישות קדם

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

רמז 1

מכונה דטרמיניסטית היא מקרה פרטי של אי־דטרמיניסטית.

רמז 2

סיירו בעץ חישוב לעומק תוך שמירת קונפיגורציות.

רמז 3

הוכחה יחסית נשארת נכונה לאחר הוספת אותו אורקל שרירותי לכל המכונות.

בנייה מודרכת

מחסום הרלטיביזציה

שלב 1 מתוך 6
שני עולמות אורקל החולקים מכונה אחתמכונת אורקל אחת מזינה את אותה שרשרת הכלות P^O ⊆ NP^O ⊆ PSPACE^O לעולם A, שבו המחלקות שוות, ולעולם B, שבו הן מופרדות.מכונת אורקל — אותה מכונה בשני העולמותMסרט עבודהכתיבת qסרט שאילתותצעד אחדאורקל Oq ∈ Oq ∉ Oכתיבת q עולה זמן, ולכן השאילתות נשארות באורך פולינומי.
מבנה משותף — נכון לכל אורקל

פתרון מלא

עבור שפה קבועה AA, המחלקה PAP^A כוללת שפות שמכונת אורקל דטרמיניסטית מכריעה בזמן פולינומי, כאשר תשובה לשאילתה עולה צעד אחד; בניית השאילתה עדיין עולה זמן. NPANP^A מוגדרת באופן אי־דטרמיניסטי.

מכונה דטרמיניסטית היא מקרה פרטי של אי־דטרמיניסטית, ולכן PA⊆NPAP^A\subseteq NP^A. מכונת NPANP^A בזמן p(n)p(n) יוצרת עץ חישוב בעומק פולינומי וקונפיגורציות באורך פולינומי. מכונה דטרמיניסטית מסיירת בעץ לעומק, שומרת קונפיגורציה ומוני ענפים, ומבצעת אותן שאילתות אורקל. הזמן עשוי להיות אקספוננציאלי אך המקום פולינומי, ולכן NPA⊆PSPACEANP^A\subseteq PSPACE^A.

הוכחה יחסית ל-P=NPP=NP הייתה מוכיחה PO=NPOP^O=NP^O לכל אורקל OO, בסתירה לבחירת O=BO=B. הוכחה יחסית להפרדה הייתה סותרת את העולם O=AO=A. לכן פתרון מלא חייב לכלול רכיב מכריע שאינו יחסי.

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

נקודות בדיקה

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

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

  • הסקת P≠NPP\ne NP ממשפט האורקלים.
  • הנחת כתיבת שאילתה אקספוננציאלית בצעד.
  • ביטול סימוני אורקל באופן אלגברי.

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

  • Arora-Barak draft, sec. 3.4
  • Papadimitriou, ch. 14
  • הערת כיסוי הקורפוס: אין כיסוי ישיר בסיכום הממוזג או בתמלילי 2026.
  • מיפוי קטלוג: data/exercises.json; הניסוח והפתרון עצמאיים; הגשות אישיות אינן מקור סמכות.

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

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

פתיחה בגלריית ההמחשות: מחסום הרלטיביזציה