מפת הסיבוכיות
EN
יחידה 10

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

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

מטרות

  • לפרוס רמות נמוכות של PH כפסוקים מכומתים.
  • לפרש מכונות אורקל ומחלקות יחסיות.
  • לנסח את מחסום הרלטיביזציה בלי להפוך אותו לתוצאת הפרדה.
  • לסקור מעגלים ואת P/poly\mathrm{P/poly} תוך הבחנה בין אחידות לאי־אחידות.

הודעת היקף — העשרה מספרי הלימוד. הסיכום הסטודנטיאלי הממוזג בן 142 העמודים אינו מכסה יחידה זו במידה מספקת. זהו חומר העשרה מעבר לסיכום, הנשען בעיקר על Sipser, ‏Arora–Barak ו-Papadimitriou. זהו סקר זהיר, לא קורס מלא בסיבוכיות מעגלים.

1. ההיררכיה הפולינומיאלית באמצעות כמתים

שפה שייכת ל-ΣkP\Sigma_k^P אם קיימים פולינום pp ויחס RR הניתן לחישוב בזמן פולינומי כך ש-

x∈L  ⟺  ∃y1∈{0,1}p(∣x∣)∀y2∈{0,1}p(∣x∣)⋯Qkyk  R(x,y1,…,yk)=1,x\in L\iff \exists y_1\in\{0,1\}^{p(|x|)} \forall y_2\in\{0,1\}^{p(|x|)} \cdots Q_k y_k\; R(x,y_1,\ldots,y_k)=1,

כאשר יש kk בלוקים מתחלפים והראשון קיומי. ΠkP\Pi_k^P מתחילה בכמת אוניברסלי. בבסיס:

Σ0P=Π0P=P,Σ1P=NP,Π1P=coNP.\Sigma_0^P=\Pi_0^P=\mathrm P,\qquad \Sigma_1^P=\mathrm{NP},\qquad \Pi_1^P=\mathrm{coNP}.

ברמה השנייה:

x∈L∈Σ2P  ⟺  ∃y ∀z  R(x,y,z),x∈L∈Π2P  ⟺  ∀y ∃z  R(x,y,z).\begin{aligned} x\in L\in\Sigma_2^P&\iff\exists y\,\forall z\;R(x,y,z),\\ x\in L\in\Pi_2^P&\iff\forall y\,\exists z\;R(x,y,z). \end{aligned}

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

PH=⋃k≥0ΣkP=⋃k≥0ΠkP.\mathrm{PH}=\bigcup_{k\ge0}\Sigma_k^P=\bigcup_{k\ge0}\Pi_k^P.

תיאור רקורסיבי שקול הוא

Σk+1P=NPΣkP,Πk+1P=coNPΣkP,\Sigma_{k+1}^P=\mathrm{NP}^{\Sigma_k^P}, \qquad \Pi_{k+1}^P=\mathrm{coNP}^{\Sigma_k^P},

עם ניסוחי אורקל שקולים מקובלים. השקילות שימושית, אך אינה מתירה להפוך סדר כמתים.

דוגמה פתורה. השאלה אם קיימת השמה ל-yy כך שהנוסחה φ(y,z)\varphi(y,z) נכונה לכל השמה ל-zz נמצאת ב-Σ2P\Sigma_2^P:

∃y ∀z  φ(y,z)=1.\exists y\,\forall z\;\varphi(y,z)=1.

עבור φ=y∨z\varphi=y\lor z, הבחירה y=1y=1 עובדת. עבור φ=y⊕z\varphi=y\oplus z, אין yy יחיד ששורד את שני ערכי zz.

2. לוגיקת קריסה

אם P=NP\mathrm P=\mathrm{NP}, אז גם P=NP=coNP\mathrm P=\mathrm{NP}=\mathrm{coNP}. באינדוקציה, מכונה פולינומית עם שאילתות NP מחליפה כל שאילתה באלגוריתם P, ולכן כל רמה נוספת נשארת P:

P=NP⟹PH=P.\mathrm P=\mathrm{NP}\quad\Longrightarrow\quad\mathrm{PH}=\mathrm P.

משפט קריסה כללי יותר אומר שאם ΣkP=ΠkP\Sigma_k^P=\Pi_k^P, אז PH קורסת לרמה kk. ההוכחה ממזגת בלוקי כמתים סמוכים שווי־כוח או משתמשת באפיון האורקלי. זו טענה מותנית; לא ידוע שוויון כזה עבור k≥1k\ge1.

3. מכונות אורקל ומחלקות יחסיות

למכונת אורקל עבור שפה AA יש סרט שאילתה ומצב מיוחד. בצעד יחיד היא מקבלת תשובה אם המחרוזת שעל הסרט שייכת ל-AA. מותרות שאילתות אדפטיביות רבות באורך פולינומי. המחלקות היחסיות מסומנות PA,NPA\mathrm P^A,\mathrm{NP}^A.

האורקל הוא פרימיטיב מופשט, לא טענה ש-AA כריעה או ניתנת למימוש זול. חייבים להשאיר את אותו אורקל בהשוואה:

PA⊆NPA\mathrm P^A\subseteq\mathrm{NP}^A

לכל AA, אך ההתנהגות יכולה להשתנות בין עולמות אורקל.

דוגמה. SAT נמצאת ב-PSAT\mathrm P^{\mathrm{SAT}} בשאילתה אחת. אפשר לשחזר השמה בעזרת שאילתות אדפטיביות: שואלים אם הנוסחה נשארת ספיקה תחת x1=0x_1=0, שומרים בחירה ספיקה וממשיכים. לכן גישת אורקל חזקה משיחת many-one יחידה.

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

שיטת הוכחה מרלטבת אם כל צעד בה נשאר תקף כאשר לכל המכונות ניתן אותו אורקל שרירותי AA. סימולציות וטיעוני אלכסון רבים מרלטבים. Baker, Gill ו-Solovay בנו אורקלים A,BA,B כך ש-

PA=NPAאבלPB≠NPB.\mathrm P^A=\mathrm{NP}^A \qquad\text{אבל}\qquad \mathrm P^B\ne\mathrm{NP}^B.

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

זהו מחסום על שיטות הוכחה, לא ראיה לכך ש-P=NP\mathrm P=\mathrm{NP} או לכך שהן שונות. הפרדת אורקל אינה גוררת הפרדה רגילה, ושוויון אורקלי אינו גורר שוויון רגיל. כדי לומר שמשפט מרלטב יש לבדוק שכל שלב סובל גישת אורקל.

5. מעגלים בוליאניים ואי־אחידות

מעגל בוליאני הוא DAG סופי של קלטים ושערים כגון AND, OR, NOT. הגודל הוא מספר השערים והעומק הוא המסלול הארוך מקלט לפלט. משפחה {Cn}\{C_n\} מכריעה LL אם CnC_n נכון לכל קלט בן nn ביטים.

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

P/poly={L:קיימת משפחת מעגלים פולינומית המכריעה את L}.\mathrm{P/poly} =\{L:\text{קיימת משפחת מעגלים פולינומית המכריעה את }L\}.

אין דרישה שאלגוריתם יעיל יחיד ייצר את CnC_n. זו אי־אחידות. מתקיים

P⊆P/poly,\mathrm P\subseteq\mathrm{P/poly},

כי אפשר לפרוש חישוב TM פולינומי למעגל פולינומי לכל אורך קלט, אך לא ידוע שוויון.

אפיון העצה הוא

P/poly=⋃pP/p(n),\mathrm{P/poly}=\bigcup_p\mathrm P/p(n),

כאשר מכונה פולינומית מקבלת עצה ana_n התלויה רק באורך הקלט ובאורך לכל היותר p(n)p(n). בכיוון אחד מקודדים את CnC_n כעצה; בכיוון השני מקמפלים את המכונה הקבועה והעצה למעגל.

עצה לא־אחידה עשויה לקודד מידע שרירותי תלוי־אורך. כל שפה אונרית U⊆{1}∗U\subseteq\{1\}^* נמצאת ב-P/poly באמצעות ביט עצה שאומר אם 1n∈U1^n\in U, אפילו אם UU אינה כריעה. לכן P/poly אינה מחלקה אחידה רגילה של אלגוריתמים אפקטיביים.

עובדות מבניות זהירות

  • קיום מעגלים קטנים לבעיה אינו נותן אוטומטית דרך יעילה לבנות אותם.
  • חסם תחתון סופר־פולינומי למעגלים כלליים עבור שפה מפורשת יביא הפרדות מרכזיות; חסם כזה אינו ידוע.
  • משפט Karp–Lipton אומר שאם NP⊆P/poly\mathrm{NP}\subseteq\mathrm{P/poly} אז PH קורסת ל-Σ2P\Sigma_2^P. כאן הוא מובא להתמצאות בלבד.
  • קיימים חסמים חזקים למודלי מעגלים מוגבלים; אין להכלילם למעגלים כלליים.

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

  • להפוך ∃y∀z\exists y\forall z ל-∀z∃y\forall z\exists y.
  • לאפשר מספר חילופים גדל ועדיין לקרוא לכך רמת PH קבועה.
  • להתייחס לאורקל כאל ספרייה ממשית בזמן קבוע.
  • להסיק הפרדה רגילה מעולם אורקל יחיד.
  • להניח שמעגלים פולינומיאליים ניתנים לבנייה אחידה.
  • להסיק P=P/poly\mathrm P=\mathrm{P/poly} מההכלה בלבד.
  • להכליל חסם למעגלים מוגבלים לכל המעגלים.

המחשות

בנייה מודרכת

סריג ההיררכיה הפולינומית

שלב 1 מתוך 6
Σ₀ᴾ = Π₀ᴾ = Pפרדיקט בזמן פולינומי
מתחילה בכמת קיומימתחילה בכמת אוניברסלי

מציירים שני צירים: חילופי כמתים אנכיים ב-PH, ותנועה אופקית מאחידות לאי־אחידות מ-P אל P/poly. עולמות אורקל מוצגים כשכבות שקופות נפרדות, לא כהכלה נוספת.

תרגילים

תרגיל 1 — סיווג Σ2P\Sigma_2^P

סווגו את השפה המוגדרת על ידי ∃y ∀z R(x,y,z)\exists y\,\forall z\,R(x,y,z) כאשר R∈PR\in\mathrm P ו-∣y∣,∣z∣|y|,|z| פולינומיאליים.

פתרון

זו בדיוק Σ2P\Sigma_2^P: כמת קיום חיצוני ואחריו כמת אוניברסלי, עם יחס פולינומיאלי.

תרגיל 2 — ∃∀\exists\forall מול ∀∃\forall\exists

הוכיחו לוגית מדוע ∃y∀z R\exists y\forall z\,R אינו שקול ל-∀z∃y R\forall z\exists y\,R בכלל.

פתרון

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

תרגיל 3 — מחסום רלטיביזציה

מה בדיוק שוללים שני עולמות אורקל עם PA=NPAP^A=NP^A ועם PB≠NPBP^B\neq NP^B?

פתרון

הם שוללים הוכחה מרלטבת אחידה ל-P מול NP: כל הוכחה כזו הייתה נשמרת בשני העולמות. הם אינם מכריעים את השאלה הלא־יחסית בעולם האמיתי.

תרגיל 4 — מ-P למעגלים

הוכיחו שכל שפה ב-P\mathrm P שייכת ל-P/poly\mathrm{P/poly}.

פתרון

לכל אורך nn פורשים את חישוב המכונה הפולינומיאלית למעגל גודל פולינומי (טבלת קונפיגורציות/שערים מקומיים). המשפחה {Cn}\{C_n\} מכריעה את השפה; העצה יכולה להיות תיאור המעגל.

תרגיל 5 — P/poly ושפות לא כריעות

הוכיחו ש-P/poly\mathrm{P/poly} יכולה להכיל שפה לא כריעה. איזו עצה משמשת לשפה אונרית?

פתרון

לכל שפה אונרית L⊆{1}∗L\subseteq\{1\}^*, הביט an=[1n∈L]a_n=[1^n\in L] הוא עצה באורך 11. המעגל בודק אונריות ומוציא את ana_n. אפשר לבחור LL לא כריעה.

סיכום

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

תרגול מודרך

משימה 1 — משלים של Σ2P\Sigma_2^P

הוכיחו תחבירית co⁡Σ2P=Π2P\operatorname{co}\Sigma_2^P=\Pi_2^P.

פתרון

x∉L  ⟺  ∀y ∃z ¬Rx\notin L\iff\forall y\,\exists z\,\neg R כאשר RR פולינומיאלי נשאר פולינומיאלי תחת שלילה. זהו אפיון המשלים, לא הוכחה ש-Σ2P=Π2P\Sigma_2^P=\Pi_2^P.

משימה 2 — עצה לפי אורך

מדוע עצה נפרדת לכל קלט xx אינה מודל P/poly\mathrm{P/poly}?

פתרון

עצה לכל xx יכולה לשמור את התשובה ותכריע כל שפה. ב-P/poly\mathrm{P/poly} אותה עצה ana_n משותפת לכל הקלטים באורך nn.

משימה 3 — קריסה מ-P=NP\mathrm P=\mathrm{NP}

הוכיחו שאם P=NP\mathrm P=\mathrm{NP} אז PH=P\mathrm{PH}=\mathrm P.

פתרון

מ-P=NP\mathrm P=\mathrm{NP} גם P=coNP\mathrm P=\mathrm{coNP}. מסירים רמת כמת אחר רמת כמת בהשראת ההגדרה הרקורסיבית של PH, עד לקריסה ל-P\mathrm P. ההנחה חייבת להיות שוויון, לא הכלה חלקית.

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

  • ראיות מן הסיכום הסטודנטיאלי (היקף בלבד): סיכומי שיעור/סיכום ממוזג.pdf כולל רק אזכור של PH בסדר היום בעמ׳ 102 וחומר על אי־דטרמיניזם חסום בעמ׳ 134–135. טיפול מהותי ב-PH, באורקלים, ברלטיביזציה, במעגלים וב-P/poly אינו מופיע בו. לכן הדף הוא במפורש העשרה מבוססת ספרי לימוד מעבר לסיכום הממוזג; אין כאן טענה שנושאים מהותיים אלה נבדקו בסיכום.
  • סמכות עיקרית: Arora–Barak, טיוטת 2007: §3.5 עמ׳ 70–72 (אורקלים ומגבלות אלכסון), פרק 5 §§5.1–5.5 עמ׳ 91–99 (PH ואפיון אורקלי), פרק 6 §§6.1–6.3 עמ׳ 101–107 (מעגלים, עצה, Karp–Lipton).
  • הצלבות: Sipser, מהדורה 3, §9.2 עמ׳ 376–379, §9.3 עמ׳ 379–388, §10.3 עמ׳ 408–415; Papadimitriou, §14.3 עמ׳ 339–343, פרק 17 §§17.1–17.2 עמ׳ 411–433, ופרק 11 §11.4 עמ׳ 267–278.
  • מצב עריכתי: כל ההגדרות והטענות על קריסה ומחסום נבדקו בסעיפים אלה. Karp–Lipton ותוצאות למעגלים מוגבלים הן טענות סקר בלבד. נבדק; ביטחון גבוה בהיקף המוצהר.