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

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

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

ישנן מספר דרכים שקולות להגדיר את ההיררכיה. בכולן מוגדרות שלוש סדרות של מחלקות: $\ \Delta _{n}^{P},\Sigma _{n}^{P},\Pi _{n}^{P}$ (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_{1}y_{2}$, שהוא עדיין חסום פולינומית באורכו. לכן מתקיים $L\in \Sigma _{j}$. כלומר הוכחנו את ההכלה הלא טריוויאלית ולכן $\Sigma _{j+1}\subseteq \Sigma _{j}$. כלומר, הוכחנו באינדוקציה כי:

$\forall j\geq i,\ \Sigma _{j}=\Sigma _{i}\implies PH=\Sigma _{i}$