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

בתורת הסיבוכיות, ההיררכייה הפולינומית היא אוסף של מחלקות סיבוכיות שמכלילות את המחלקות 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 אך לא ידוע אם קיים שוויון. מכיוון שב-PSPACE קיימות בעיות שהן PSPACE-שלמות (כדוגמת TQBF), שוויון פירושו שההיררכייה קורסת החל ממקום מסוים (כי אם קיים שוויון, הרי ש-TQBF שייכת לאיבר כלשהו בהיררכייה, ולכן החל ממנו ההיררכייה לא תוסיף לגדול).

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