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

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

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

אם A^B מסמל את המחלקה של שפות שמכונת טיורינג מסוג A יכולה לקבל כשיש לה אורקל לשפה ב-B, אז מגדירים:
\Delta_{i+1}^P = P^{\Sigma_i^P},
\Sigma_{i+1}^P = NP^{\Sigma_i^P},
\Pi_{i+1}^P = coNP^{\Sigma_i^P}.

כמתים (quantifiers) הם מילים כמו "קיים" (\exists) ו"לכל" (\forall).\Sigma_n מכילה שפות שמתוארות על ידי פורמולה עם n כמתים כשהראשון הוא "קיים". \Pi_n דומה אבל עם כמת ראשון של "לכל".
באמצעות פעולות של הוספת כמתים לשפה C מגדירים \exists^{P}C ו-\forall^{P}C, ואז:
\Sigma_{k+1}^{P} = \exists^{P}\Pi_k^{P},
\Pi_{k+1}^{P} = \forall^{P}\Sigma_k^{P}.

מההגדרות נובעים הכלות בסיסיות כמו
\Sigma_i^{P} \subseteq \Delta_{i+1}^{P} \subseteq \Sigma_{i+1}^{P}
והקשר דואלי \Sigma_i^{P} = \mathrm{co}\,\Pi_i^{P}.
לא ידוע אם הכלות האלה הן קפדניות או שהן שוויונות במקרים מסוימים. אם קיימת שוויון מסוים, ההיררכיה "קורסת": כלומר כל רמות גבוהות יותר שוות לרמה מסוימת. למשל, אם P=NP, ההיררכיה קורסת והכל שווה ל-P.

איחוד כל המחלקות בהיררכיה מסומן PH. ידוע ש-PH כלול ב-PSPACE (המחלקה של בעיות שנפתרות בזמן פולינומי מבחינת השימוש בזכרון). אבל לא ידוע אם PH=PSPACE.

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

אם \Sigma_i = \Pi_i עבור i כלשהו, אז PH = \Sigma_i = \Pi_i. המשמעות היא שאם רמה אחת שווה לדואלי שלה, כל הרמות עוצרות לה.
הרעיון בהוכחה הוא שמניחים \Sigma_j = \Pi_j ומראים ש-\Sigma_{j+1} \subseteq \Sigma_j על ידי החלפת סדר הכמתים והשילוב של שני כמתים ראשונים ליחיד שמוגבל פולינומית. מכאן נובע שייווצר שוויון לכל הרמות מעל j.

דוגמא טבעית: בעיית הקביעה האם קיימת קבוצה בלתי תלויה בגודל לפחות k בגרף G (המסומנת \alpha(G)\ge k) היא ב-\Sigma_1^P, כי אפשר פשוט "למצוא" קבוצה כזאת (פסוק עם "קיים"). ההשוואה \alpha(G)\le k היא ב-\Pi_1^P.
השפה שבה \alpha(G)=k נמצאת ב-\Sigma_2^P, כי אפשר לתאר אותה באמצעות "קיים" ואחריו "לכל".
עוד דוגמה: השפה של פונקציות בוליאניות שהן זהות לפונקציה שמסומנת על ידי מעגל בוליאני עם k שערים היא ב-\Sigma_2^P.

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

ההיררכיה הפולינומית היא דרך לסדר בעיות קשות לפי רמות. היא כוללת קבוצות כמו P, NP ו-co-NP.

אורקל זה כלי מדומה. מכונה יכולה לשאול אותו שאלה ולקבל תשובה מיד. זה עוזר להגדיר יכולות חזקות יותר.
כמתים הם מילים לוגיות. "קיים" אומר שיש משהו. "לכל" אומר שכולם מקיימים תנאי.

הדרגה הראשונה היא P. כל דרגה חדשה מוסיפה יכולת לשאול אורקל של הדרגה הקודמת או להוסיף כמתים.
כך מקבלים רמות \Sigma_n ו-\Pi_n שונה זו מזו לפי סדר הכמתים.

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

דוגמה: בעיה של "האם יש קבוצה גדולה של קודקודים בגרף בלי חיבור ביניהם" שייכת ל-\Sigma_1^P. זאת כי אפשר "להראות" את הקבוצה שקיימת.
הבעיה "האם הגודל בדיוק k" יכולה לדרוש שתי רמות של כמתים, ולכן היא ב-\Sigma_2^P.

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