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

נתבונן ב 3 הבעיות הבאות :

1. $clique$ - $\{(G,k)|\text{G has k vertex with all the possible edges}\}$
2. $\overline{clique}$ - $\{(G,k)|\text{G does not contains a k-size clique}\}$
3. $maxClique$ - $\{(G,k)|\text{k is the maximal size clique in G}\}$

הראשונה שייכת ל NP שכן העדות יכולה להיות פשוט $k$ קודקודים מהגרף.
השנייה כמובן שייכת ל CONP.
לאן שייכת $maxClique$ ?
כדי ש $(G,k)$ יהיה שייך ל $maxClique$ צריך להראות ש

1. ב $G$ קיים קליק בגודל $k$.
2. לכל קבוצת קודקודים ב $G$ בגודל העולה על $k$, קבוצה זאת אינה קליק.

כלומר את הבעיה הזאת אנחנו מתארים באמצעות שתי כמתים, בניגוד לבעיות $NP,CONP$ שאפשר לתאר אותן עם כמת אחד בלבד.

אם כן $maxClique\in {\mathrm{\Sigma }}_2$ שאותו נגדיר באמצעות ההירכייה הפולינומית:

הגדרה נאמר כי $S\in {\mathrm{\Sigma }}_k$ אמ״מ קיים מוודא פולינומי כך ש

כאשר: $Q_{}=\mathrm{\exists }$ אם $k$ אי זוגי ו $Q_{}=\mathrm{\forall }$ אחרת.
וגם קיים פולינום $P$ כך ש

למשל: $S\in {\mathrm{\Sigma }}_2$ אם קיים פולינום $P$ ואלגוריתם פולינומי $V$ כך ש

טענה:

לא אתעמק בהוכחה בסיכום זה אך ניתן להראות באינדוקצייה שאם $s\in {\mathrm{\Sigma }}_i$ אז המוודא החדש יוכל לקבל $i+1$ עדים ולהשתמש במודוא המקורי תוך התעלמות מהעדות האחרונה כך ש $s\in {\mathrm{\Sigma }}_{i+1}$ .

הגדרה נאמר כי $S\in {\mathrm{\Pi }}_k$ אמ״מ קיים מוודא $V_S$ כך ש

כאשר: $Q_{}=\mathrm{\exists }$ אם $k$ זוגי ו $Q_{}=\mathrm{\forall }$ אחרת.
וגם קיים פולינום $P$ כך ש

טענה
תחת אותה הוכחה נוכל להראות ש

טענה

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

משפט קריסת ההירכייה

או במילים אחרות

כדי להוכיח את הטענה הזאת ולענות על השאלה שלנו נרצה לתת מספר למות עזר ואת הוכחותיהן

למה 1 :
$S\in {\mathrm{\Sigma }}_{k+1}$ אמ״מ קיים פולינום $P$ ובעיה $S^{\prime }\in {\mathrm{\Pi }}_k$ כך ש

הוכחת למה 1:
$\leftarrow$ :
תהי $S\in {\mathrm{\Sigma }}_{k+1}$ , לפי הגדרת ${\mathrm{\Sigma }}_{k+1}$ קיים מוודא $V_S$ ופולינום $P$ כך ש

וגם

נגדיר את $S^{\prime }$ לקבל $(x,y_1)$ כך ש

נשים לב ש $S^{\prime }\in {\mathrm{\Pi }}_k$ ועבור אותו פולינום $P$ שחוסם את $|y_1|$ תחת הבעיה $S$ יתקיים שהוא חוסם את $|y_1|$ תחת הבעיה $S^{\prime }$.

$\to$ :
אם קיים $S^{\prime }\in {\mathrm{\Pi }}_k$ ופולינום $P$ המקיים $x\in S\leftrightarrow {\mathrm{\exists }}_{y:|y|\le P(|x|)}:(x,y)\in S^{\prime }$ אזי $S\in {\mathrm{\Sigma }}_{k+1}$ שכן קיים מוודא $V_{S^{\prime }}$ פולינומי, ופולינום $P^{\prime }$ כך שלפי הגדרה :

וגם $|y_i|\le P^{\prime }(|x,y|)$

נשים לב אם כן שמהנתונים ומההגדרה מתקיים

כך ש $|y_i|\le P^{\prime }(|x,y|)$ וגם $|y|<P(|x|)$

קיבלנו בעצם ביטוי מהצורה של ${\mathrm{\Sigma }}_{k+1}$ , נוכל אם כן להגדיר אם כן

והוא מוודא מתאים לקריטריון לכך ש $S\in {\mathrm{\Sigma }}_{k+1}$ .

המשמעות של הלמה היא שניתן לעבור מבעיה ב ${\mathrm{\Sigma }}_{k+1}$ לבעיה ב ${\mathrm{\Pi }}_k$ והפוך

למה 2 :
עבור $k\ge 1$ אם ${\mathrm{\Pi }}_k\subseteq {\mathrm{\Sigma }}_k$ אזי ${\mathrm{\Sigma }}_k={\mathrm{\Sigma }}_{k+1}$ .

הוכחת למה 2:
נניח ${\mathrm{\Pi }}_k\subseteq {\mathrm{\Sigma }}_k$ ונרצה להראות ${\mathrm{\Sigma }}_{k+1}\subseteq {\mathrm{\Sigma }}_k$ . תהי $S\in {\mathrm{\Sigma }}_{k+1}$ . לפי למת עזר 1 נובע כי קיימת $S^{\prime }\in {\mathrm{\Pi }}_k$ ופולינום $P$ כך ש

מההנחה שלנו ש ${\mathrm{\Pi }}_k\subseteq {\mathrm{\Sigma }}_k$ נקבל ש $S^{\prime }\in {\mathrm{\Sigma }}_k$ כלומר :

וכן $|y_i|\le P^{\prime }(|x,y|)$. סך הכל נקבל ש

קיבלנו סדרה של שני כמתי קיים רצופים ולכן נוכל להגדיר מוודא $y_0=y\circ y_1$ ולאחד לכמת אחד ולקבל

כל שנשאר לעשות הוא להגדיר את המוודא של $S$ להיות

כלומר הוא סך הכל יקבל את הקלט בצורה שונה.
מכאן מתקיים ש $S\in {\mathrm{\Sigma }}_k$ כנדרש.

למה 3 :

טענה זו גוררת באופן ישיר שאם ${\mathrm{\Sigma }}_0={\mathrm{\Sigma }}_1$ אזי $P=NP$ וזה אומר שכל ההירכייה קורסת.

הוכחת למה 3:
נניח ש ${\mathrm{\Sigma }}_k={\mathrm{\Sigma }}_{k+1}$ .
מלמה 2 נרצה להראות ש ${\mathrm{\Pi }}_{k+1}\subseteq {\mathrm{\Sigma }}_{k+1}$ ונקבל ${\mathrm{\Sigma }}_{k+1}={\mathrm{\Sigma }}_{k+2}$ .
מהגדרת ההירכייה כבר יש לנו ש ${\mathrm{\Pi }}_k\subseteq {\mathrm{\Sigma }}_{k+1}$ .
מההנחה שלנו מתקיים ש

כי מתקיים ${\mathrm{\Pi }}_k=\overline{{\mathrm{\Sigma }}_k}$ לכל $k$.

אם כן סך הכל נקבל

כי ${\mathrm{\Pi }}_{k+1}={\mathrm{\Pi }}_k\subseteq {\mathrm{\Sigma }}_{k+1}$ ומטענת העזר הקודמת נקבל ${\mathrm{\Sigma }}_{k+1}={\mathrm{\Sigma }}_{k+2}$ .

את משפט קריסת ההירכיה כעת אפשר להוכיח ישירות באמצעות למה 3
אם $P=NP$ אזי ${\mathrm{\Sigma }}_0={\mathrm{\Sigma }}_1$ ולכן מלמה 3 השיוויון חל לכל $k$ . כלומר

כעת נוכל להתחיל לענות על השאלה ששאלנו למעלה , איך ניתן להסיק שאם יש רדוקציית קוק מ $A$ ל $B\in {\mathrm{\Sigma }}_k$ אז $A\in PH$?

נרצה להסתכל על מכונות טיורינג לא דטרמניסטיות בעלת גישת אורקל ל $B$.

1. נסמן: $N{P}^B$ מחלקת הבעיות שניתן לפתור על ידי מכונת טיורינג פולינומית לא דטרמינסטית בעלת גישת אורקל ל $B$.
2. נסמן: $P^B$ מחלקת הבעיות שניתן לפתור על ידי מכונת טיורינג פולינומית דטרמינסטית בעלת גישת אורקל ל $B$.
3. נסמן: $P^{NP}$ מחלקת הבעיות שניתן לפתור על ידי מכונת טיורינג פולינומית דטרמינסטית בעלת גישת אורקל ל $B\in NP$.
4. נסמן: $N{P}^{NP}$ מחלקת הבעיות שניתן לפתור על ידי מכונת טיורינג פולינומית לא דטרמינסטית בעלת גישת אורקל ל $B\in NP$.

משפט: אם יש רדוקציית קוק מ $A$ ל $B\in NP$ אזי: $A\in P^{NP}\subseteq N{P}^{NP}=N{P}^{{\mathrm{\Sigma }}_1}$ .

מכונת טיורינג לא דטרמינסטית

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

מ״ט ל״ד יכולה לקיים את התכונות הבאות:

1. פולינומית - מספר הצעדים בכל מסלולי החישוב הוא פולינומי בגודל הקלט
2. בעל גישת אורקל- יכולה להפעיל שאילתות לבעיות ההכרעה ב$NP$ בעלות של צעד בודד.

משפט:
לכל $k\ge 0$ מתקיים

נוכיח בהכלה דו כיוונית-
$\supseteq$ :
תהי $S\in {\mathrm{\Sigma }}_{k+1}$ , נוכיח ש $S\in N{P}^{{\mathrm{\Sigma }}_k}$ .
נשים לב ראשית לתכונה הבאה

זה נובע בגלל ש ${\mathrm{\Pi }}_k=CO{\mathrm{\Sigma }}_k$ כלומר, כיוון שהתשובות של האורקל נכונות תמיד, לענות על השאלה האם $x\in S^{\prime }\in {\mathrm{\Sigma }}_k$ זה שקול ללענות על השאלה האם $x\in \overline{S^{\prime }}\in {\mathrm{\Pi }}_k$.

כמו כן נזכר בלמה שאומרת

נראה שאם $S\in {\mathrm{\Sigma }}_{k+1}$ אז $S\in N{P}^{{\mathrm{\Sigma }}_k}=N{P}^{{\mathrm{\Pi }}_k}$

עבור $S$ כנ״ל נבנה מ״ט פולינומית ל״ד שמכריעה את $S$ על ידי גישת אורקל ל $S^{\prime }\in {\mathrm{\Pi }}_k$ שהיא הבעיה המובטחת מהלמה הנ״ל.

$M_S(x)$ :

1. הגרל $|y|\le P(|x|)$ (הפולינום המתאים מהלמה)
2. פנייה לאורקל על $S^{\prime }$ ושאלה האם $(x,y)\in S^{\prime }$ והחזרת התשובה.

מהלמה נובע כי אם $x\in S$ אזי קיים $y$ שיגרום למכונה $M_S$ לקבל את $x$ כי ישנו איזה $y$ שעבורו $(x,y)\in S^{\prime }$.
אחרת, אם $x\notin S$ אזי לכל $y$, $(x,y)\notin S^{\prime }$ ולכן $M_S$ דוחה כלומר ל $M_S$ אין מסלול.

ז״א ש $S\in N{P}^{{\mathrm{\Pi }}_k}=N{P}^{{\mathrm{\Sigma }}_k}$ כדרוש.

$\subseteq$ :
נניח כי $S\in N{P}^{{\mathrm{\Sigma }}_k}$ ונוכיח כי $S\in {\mathrm{\Sigma }}_{k+1}$
בלי הגבלת הכלליות נניח שהמכונה טיורינג ל״ד שמכריע בקריאות לאורקל היא מכונה כזו שמגרילה תשובות בלי קריאה לאורקל ורק אם כל ההגרלות מתקבלות על ידי המכונה, האורקל בודק את כל ההגרלות ויחזיר $1$ אם כל ההגרלות נכונות גם מבחינת האורקל.
המטרה היא להפריד את ה״לוגיקה״ של המכונה לבין הפניות לאורקל.

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

עבור קלט $x$ והגרלות $y$ של המכונה הלא דטרמנסטית,
נסמן ב $q(x,y)$ את מספר השאלות שרוצים לשאול באורקל.
נסמן ב $q^i(x,y)$ את השאלה ה $i$ מבין $q(x,y)$ שאלות (שאילתה אל מול האורקל)
נסמן ב $a^i(x,y)$ את הניחוש ה $i$

מתקיים ש

כאשר $A$ זה החלק הביצועי של המכונה בלי פניות לאורקל.
נזכיר שנרצה להראות ש $x\in S$ אם הוא ביטוי מהצורה של ${\mathrm{\Sigma }}_k$ .

נשים לב ש $E_1\leftrightarrow E_2$ זה שקול לוגית ל $(E_1^i\wedge E_2^i)\vee (⌝E_1^i\wedge ⌝E_2^i)$

נציב ונקבל :

כעת נסתכל על הבעיה $S^{\prime }\in {\mathrm{\Sigma }}_k$ הבעיה שאליה נעשת הפניית אורקל.
לבעיה זא קיים מוודא פולינומי $V_{S^{\prime }}$ ופולינום $P_{S^{\prime }}$ כך ש:

באותו אופן :

הדבר נכון גם עבור השאילתות ה $q^i$ שרשמנו למעלה. בסופן של דבר נוכל להציב את הנ״ל בביטוי $(E_1^i\wedge E_2^i)\vee (⌝E_1^i\wedge ⌝E_2^i)$ עד שנקבל את הדרוש כלומר $S\in {\mathrm{\Sigma }}_{k+1}$.

אם כן , הוכחנו ש ${\mathrm{\Sigma }}_{k+1}=N{P}^{{\mathrm{\Sigma }}_k}$ .

סגירות רדוקציית קוק

תהי $A$ כלשהי ו $B\in {\mathrm{\Sigma }}_k$ אזי,
אם ישנה רדוקציית קוק מ $A$ ל $B$ כלומר ישנה מ״ט פולינומית דטרמיניסטית בעלת גישת אורקל ל $B$ שמכריעה את $A$ ונסמן אותה $A\in P^B$

ברור כי $P^B\subseteq N{P}^B$ כי המודל הדטרמיניסטי מוכל במודל הלא דטרמיניסטי של מ״ט.
עבור $B\in {\mathrm{\Sigma }}_k$ מקבלים ש $A\in N{P}^{{\mathrm{\Sigma }}_k}$ ומהטענה הנ״ל מתקיים $A\in {\mathrm{\Sigma }}_{k+1}$ כלומר ישנה סגירות לרדוקציית קוק תחת $PH$ .