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

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

תוכן עניינים

1 הגדרה פורמלית
- 1.1 הגדרה באמצעות אורקל
- 1.2 הגדרה באמצעות כמתים
2 הקשרים בין המחלקות השונות בהיררכייה

[עריכה] הגדרה פורמלית

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

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

See also ebooksgratis.com: no banners, no cookies, totally FREE.

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

מתוך ויקיפדיה, האנציקלופדיה החופשית

תוכן עניינים

[עריכה] הגדרה פורמלית

[עריכה] הגדרה באמצעות אורקל

[עריכה] הגדרה באמצעות כמתים

[עריכה] הקשרים בין המחלקות השונות בהיררכייה

Views

ניווט

קהילה

חיפוש

שפות אחרות