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

בתורת הסיבוכיות, **ההיררכיה הפולינומית** היא אוסף של מחלקות סיבוכיות שמכלילות את המחלקות P, NP ו-co-NP באמצעות אורקל. ההיררכיה מספקת חלוקה עדינה של השפות השייכות למחלקה PSPACE ובכך משפרת את היכולת לסווג את הקשרים בינן.

## הגדרה פורמלית
ישנן מספר דרכים שקולות להגדיר את ההיררכיה. בכולן מוגדרות שלוש סדרות של מחלקות: \ \Delta^P_n,\Sigma^P_n,\Pi^P_n (n הוא מספר האיבר בסדרה, ואילו P בא לציין כי המחלקה P היא בסיס ההיררכיה).
### הגדרה באמצעות אורקל
כאשר מגדירים באמצעות אורקל, כל איבר בשלוש הסדרות נקבע באמצעות חיזוק של P, NP או co-NP בעזרת אורקל לאיבר הקודם בסדרה \ \Sigma_n. בצורה פורמלית, אם הסימון \ A^B עבור מחלקות סיבוכיות A,B בא לציין את מחלקת כל השפות שניתנות לקבלה על ידי מכונת טיורינג הפועלת בסיבוכיות A ובעלת אורקל לשפה מ-B, אז ההיררכיה הפולינומית מוגדרת בצורה הבאה:

בסיס ההגדרה לכל שלוש הסדרות הוא המחלקה P:

:\Delta_0^{\rm P} := \Sigma_0^{\rm P} := \Pi_0^{\rm P} := \mbox{P},

וכאמור, כל איבר בסדרות מוגדר באמצעות חיזוק על ידי אורקל של P, NP או co-NP:

:\Delta_{i+1}^{\rm P} := \mbox{P}^{\Sigma_i^{\rm P}}
:\Sigma_{i+1}^{\rm P} := \mbox{NP}^{\Sigma_i^{\rm P}}
:\Pi_{i+1}^{\rm P} := \mbox{coNP}^{\Sigma_i^{\rm P}}

### הגדרה באמצעות כמתים
בצורה לא פורמלית, ניתן לומר כי המחלקה \ \Sigma_n היא אוסף כל השפות שניתן לתאר באמצעות פסוק לוגי המכיל n כמתים שהראשון שבהם הוא הכמת \ \exists. את \ \Pi_n מגדירים בצורה דומה אך כאשר הכמת הראשון הוא \ \forall.

כדי להגדיר את התכונה הזו באופן פורמלי, משתמשים בסימון הבא בהינתן שפה L ופולינום p:
:  \exists^p L := \left\{ x \in \{0,1\}^* \ \left| \ \left( \exists w \in \{0,1\}^{\leq p(|x|)} \right) \langle x,w \rangle \in L \right. \right\}, 

כלומר, \ \exists^p L הוא אוסף המילים x שקיים עבורן המשך w שאורכו חסום על ידי הפולינום p כך ש-xw הוא מילה בשפה L. בדרך דומה מגדירים את אוסף כל המילים x ש**לכל** המשך w שלהן שחסום בידי p, xw שייכת לשפה:
:  \forall^p L := \left\{ x \in \{0,1\}^* \ \left| \ \left( \forall w \in \{0,1\}^{\leq p(|x|)} \right) \langle x,w \rangle \in L \right. \right\} 

הגדרה זו מורחבת בצורה טבעית למחלקות של שפות:
:\exists^{\rm P} \mathcal{C} := \left\{\exists^p L \ | \ p \mbox{ is a polynomial and } L \in \mathcal{C} \right\}
:\forall^{\rm P} \mathcal{C} := \left\{\forall^p L \ | \ p \mbox{ is a polynomial and } L \in \mathcal{C} \right\}

באמצעות סימונים אלו, ההיררכיה הפולינומית מוגדרת על ידי:
: \Sigma_0^{\rm P} := \Pi_0^{\rm P} := {\rm P} 
: \Sigma_{k+1}^{\rm P} := \exists^{\rm P} \Pi_k^{\rm P} 
: \Pi_{k+1}^{\rm P} := \forall^{\rm P} \Sigma_k^{\rm P} 

## הקשרים בין המחלקות השונות בהיררכיה
מהגדרת המחלקות בהיררכיה נובעים הקשרים הבאים:
:\Sigma_i^{\rm P} \subseteq \Delta_{i+1}^{\rm P} \subseteq \Sigma_{i+1}^{\rm P}
:\Pi_i^{\rm P} \subseteq \Delta_{i+1}^{\rm P} \subseteq \Pi_{i+1}^{\rm P}
:\Sigma_i^{\rm P} = {\rm co}\Pi_{i}^{\rm P}

לא ידוע אם ההכלות הללו הן הכלות ממש או שקיים שוויון בחלק מהמקרים. לא קשה להוכיח כי אם \ \ \Sigma_n^P=\Sigma_{n+1}^P או \ \Sigma_n^P=\Pi_n^P עבור \ \ n כלשהו, אז ההיררכיה קורסת: יתקיים \ \Sigma_k^P=\Pi_n^P לכל \ k>n. בפרט, אם P=NP, ההיררכיה קורסת לחלוטין וכל המחלקות בה שוות.

איחוד כל המחלקות השייכות להיררכיה הפולינומית מסומן בתור **PH**. ידוע כי PH מוכלת במחלקה PSPACE (וזאת משום שניתן למצוא בעיה שלמה לכל מחלקה \Sigma_i^P שהיא מעין בעיית TQBF חסומה במספר הכמתים, ולכן  בדומה ל־TQBF ניתן לפתור אותה ובנוסף כל שפה במחלקה במקום פולינומי, זאת משום שהרדוקציה היא בזמן פולינומי ולכן לא תדרוש יותר ממקום פולינומי) אך לא ידוע אם קיים שוויון. מכיוון שב-PSPACE קיימות בעיות שהן PSPACE-שלמות (כדוגמת TQBF), שוויון פירושו שההיררכיה קורסת החל ממקום מסוים (כי אם קיים שוויון, הרי ש-TQBF שייכת לדרגה כלשהי בהיררכיה, ובדרגה זו ההיררכיה קורסת).

ניתן להגדיר שפות הדומות ל-TQBF ומהוות שפות שלמות עבור כל אחת מהרמות בהיררכיה (כלומר, שפות שכל שפה אחרת באותה הרמה בהיררכיה ניתנת לרדוקציה פולינומית אליהן).

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

## משפט קריסת ההיררכיה
עבור ההיררכיה הפולינומית, מתקיים שאם \Sigma_i = \Pi_i , אזי PH = \Sigma_i = \Pi_i . תוצאה מידית ראשונה היא שאם P=NP  אזי ההיררכיה הפולינומית קורסת לדרגה 0, כלומר PH = P.
### הוכחה
נוכיח כי בהינתן \Sigma_j = \Pi_j  ניתן להסיק כי \Pi_{j+1} = \Sigma_{j+1} = \Sigma_j = \Pi_j עבור כל j, וכך נמשיך באינדוקציה לכל הרמות ונקבל שההיררכיה קורסת.

בכל שלב באינדוקציה, מספיק להראות כי \Sigma_j = \Pi_j \Rightarrow \Sigma_{j+1} \subseteq \Sigma_j 

לאחר שהוכחנו זאת, נקבל כי \Sigma_{j+1} = \Sigma_j ולכן גם \Pi_{j+1} = co-\Sigma_{j+1} = co-\Sigma_j = \Pi_j = \Sigma_j = \Sigma_{j+1}.

הוכחת הטענה כי \Sigma_j = \Pi_j \Rightarrow \Sigma_{j+1} \subseteq \Sigma_j :

:L \in \Sigma_{j+1} \iff \exists y_1 \forall y_2 ... Q_{j+1} y_{j+1} \ \ V(x, y_1, y_2, ... ,y_{j+1}) = 1, כאשר לכל k y_k חסום פולינומית וגם V מוודא פולינומי דטרמיניסטי שבודק שייכות ליחס R.

נוכיח שההיררכיה קורסת - ניתן לתאר מחלקה שקולה L_j  באופן הבא -
:L_j = \{(x, y_1) | \forall y_2 \exists y_3 ... Q_{j+1} y_{j+1} : (x, y_1, y_2, ...,y_{j+1}) \in R \}
אבל אנחנו יודעים ש- \Pi_j \subseteq \Sigma_j , כלומר ניתן לתאר את היחס גם כך:
:L_j = \{(x, y_1) | \exists y_2 \forall y_3 ... Q_{j+1} y_{j+1}: (x, y_1, y_2, ...,y_{j+1}) \in R \}
:ולכן קיים V'כך ש- (x,y_1) \in L_{j} \iff \exists y_2 \forall y_3 ... \bar{Q}_{j+1} y_{j+1} \ \ V'(x, y_1, y_2, ... ,y_{j+1}) = 1
:אבל x \in L \iff \exists y_1. (x,y_1)\in L_j ולכן:
:x \in L \iff \exists y_1 \exists y_2 \forall y_3 ... \bar{Q}_{j+1} y_{j+1} \ \ V'(x, y_1, y_2, ... ,y_{j+1}) = 1

וניתן לאחד את שני המשתנים הראשונים למשתנה אחד, y' = y_1y_2 , שהוא עדיין חסום פולינומית באורכו. לכן מתקיים L \in \Sigma_j. כלומר הוכחנו את ההכלה הלא טריוויאלית ולכן \Sigma_{j+1} \subseteq \Sigma_j.
כלומר, הוכחנו באינדוקציה כי:
:\forall j \ge i, \ \Sigma_j = \Sigma_i \implies PH = \Sigma_i

## דוגמאות
ניתן דוגמאות לשפות "טבעיות" בחלק מהקבוצות שהגדרנו:

בהינתן גרף G, נסמן \alpha(G) את גודל הקבוצה בלתי תלויה המקסימלית. אז שפת כל הזוגות G,k עבור גרף G ומספר k כך ש-\alpha(G)\ge k היא ב-\Sigma_1^P, כיוון שניתן למצוא פסוק המתחיל בסימני "קיים" בלבד שמתאר אותה: זה פסוק מהצורה "קיימים קודקודים v_1,...,v_k ב-G המהווים קבוצה בלתי תלויה". באופן דומה, השפה של \alpha(G)\le k היא ב-\Pi_1^P עבור הפסוק "לכל v_1,...,v_{k+1}, הקבוצה איננה בלתי תלויה".

לעומת זאת, שפת הזוגות המקיימים \alpha(G)=k איננה ידועה להיות באף אחת מהקבוצות הללו (ואם P \ne NP היא אכן לא באף אחת מהן) אך היא כן ב \Sigma_2^P, כי ניתן לתאר אותה באמצעות סימני "קיים" ואחריהם "לכל": "קיימת קבוצה v_1,...v_k כך שלכל u_1,...,u_{k+1} הקבוצה v_1,...,v_k בלתי תלויה והקבוצה u_1,...,u_{k+1} לא". בתיאור זה יכולנו להחליף את הסדר: "לכל קבוצה u_1,...,u_{k+1} קיימת קבוצה v_1,...v_k כך שהקבוצה v_1,...,v_k בלתי תלויה והקבוצה u_1,...,u_{k+1} לא". על כן, שפה זאת היא ב \Sigma^P_2\cap \Pi^P_2.

דוגמה לשפה שנמצאת ב-\Sigma_2^P ואינה ידועה להיות ב-\Pi_2^P : שפת כל הפונקציות הבוליאניות f כך שקיים מעגל בוליאני עם k שערים שזהה להן. הפסוק המתאים הוא מהצורה "קיים מעגל C כך שלכל קלט x מתקיים f(x)=C(x)" ולכן השפה ב-\Sigma_2^P.

קטגוריה:סיבוכיות חישובית