הצגת המקור של הדף "ההיררכיה הפולינומית"

ב[[תורת הסיבוכיות]], '''ההיררכיה הפולינומית''' היא אוסף של מחלקות סיבוכיות שמכלילות את המחלקות [[P (מדעי המחשב)|P]]{{כ}}, [[NP (סיבוכיות)|NP]] ו-[[co-NP]] באמצעות [[אורקל (מדעי המחשב)|אורקל]]. ההיררכיה מספקת חלוקה עדינה של השפות השייכות למחלקה [[PSPACE]] ובכך משפרת את היכולת לסווג את הקשרים בינן.

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

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

:<math>\Delta_0^{\rm P} := \Sigma_0^{\rm P} := \Pi_0^{\rm P} := \mbox{P},</math>

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

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

===הגדרה באמצעות כמתים===
בצורה לא פורמלית, ניתן לומר כי המחלקה <math>\ \Sigma_n</math> היא אוסף כל השפות שניתן לתאר באמצעות פסוק לוגי המכיל n [[כמת לוגי|כמתים]] שהראשון שבהם הוא הכמת <math>\ \exists</math>. את <math>\ \Pi_n</math> מגדירים בצורה דומה אך כאשר הכמת הראשון הוא <math>\ \forall</math>.

כדי להגדיר את התכונה הזו באופן פורמלי, משתמשים בסימון הבא בהינתן שפה L ופולינום p:
: <math> \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\}, </math>

כלומר, <math>\ \exists^p L</math> הוא אוסף המילים x שקיים עבורן המשך w שאורכו חסום על ידי הפולינום p כך ש-xw הוא מילה בשפה L. בדרך דומה מגדירים את אוסף כל המילים x ש'''לכל''' המשך w שלהן שחסום בידי p, xw שייכת לשפה:
: <math> \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\} </math>

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

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

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

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

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

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

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

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

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

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

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

:<math>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</math>, כאשר לכל k <math>y_k</math> חסום פולינומית וגם V מוודא פולינומי דטרמיניסטי שבודק שייכות ליחס R.

נוכיח שההיררכיה קורסת - ניתן לתאר מחלקה שקולה <math>L_j </math> באופן הבא -
:<math>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 \}</math>
אבל אנחנו יודעים ש- <math>\Pi_j \subseteq \Sigma_j </math>, כלומר ניתן לתאר את היחס גם כך:
:<math>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 \}</math>
:ולכן קיים <math>V'</math>כך ש- <math>(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</math>
:אבל <math>x \in L \iff \exists y_1. (x,y_1)\in L_j </math>ולכן:
:<math>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</math>

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

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

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

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

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

{{מחלקות סיבוכיות}}
[[קטגוריה:סיבוכיות חישובית]]