הפצת קריסה בהיררכיה הפולינומית

הוכחה ששוויון רמות סמוכות ב-PH מקריס את כל הרמות הגבוהות.

שאלה

נגדיר $\Sigma_0^p=\Pi_0^p=P$, וכן $\Sigma_{k+1}^p=NP^{\Sigma_k^p}$ ו-$\Pi_k^p=co\Sigma_k^p$. הוכיחו שאם $\Sigma_k^p=\Pi_k^p$ עבור $k\ge1$, אז $\mathrm{PH}=\Sigma_k^p$. פרטו את צעד האינדוקציה.

דרישות קדם

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

רמז 1

השתמשו באפיון כמתים מתחלפים.

רמז 2

החליפו פרדיקט פנימי ב-$\Pi_k^p$ בפרדיקט שקול ב-$\Sigma_k^p$.

רמז 3

שני בלוקי קיום סמוכים מתאחדים.

פתרון מלא

נראה תחילה $\Sigma_{k+1}^p\subseteq\Sigma_k^p$. עבור $L\in\Sigma_{k+1}^p$,

כאשר האורכים פולינומיים ו-$R$ פולינומי. עבור $(x,y_1)$ קבועים, החלק הפנימי מתחיל בכמת לכל ושייך ל-$\Pi_k^p$. לפי ההנחה הוא גם ב-$\Sigma_k^p$, ולכן יש לו תיאור שקול המתחיל בקיום:

לאחר ההצבה, $\exists y_1$ ו-$\exists z_1$ סמוכים ומתאחדים לבלוק קיום אחד בעל אורך פולינומי. נותרו $k$ בלוקים, ולכן $L\in\Sigma_k^p$. ההכלה ההפוכה ידועה, ומכאן שוויון.

לקיחת משלימים נותנת גם

באינדוקציה חוזרים על אותו טיעון בכל רמה גבוהה יותר. כל $\Sigma_j^p,\Pi_j^p$ עבור $j\ge k$ שוות ל-$\Sigma_k^p$, והרמות הנמוכות מוכלות בה. לכן

הצמדת עדים שומרת אורך פולינומי. עבור $k=1$ מתקבלת הטענה המותנית $NP=coNP\Rightarrow PH=NP$; השוויון עצמו אינו ידוע.

נקודות בדיקה

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

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

• מיזוג כמתים שונים לפני שימוש בהנחה.
• עצירה ברמה $k+1$ בלי אינדוקציה.
• הצגת ההנחה כעובדה ידועה.

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

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

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

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

פתיחה בגלריית ההמחשות: סריג ההיררכיה הפולינומית