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

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

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

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

ישנן מספר דרכים שקולות להגדיר את ההיררכיה. בכולן מוגדרות שלוש סדרות של מחלקות: (n הוא מספר האיבר בסדרה, ואילו P בא לציין כי המחלקה P היא בסיס ההיררכיה).

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

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

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

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

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

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

כדי להגדיר את התכונה הזו באופן פורמלי, משתמשים בסימון הבא בהינתן שפה L ופולינום p:

כלומר, הוא אוסף המילים x שקיים עבורן המשך w שאורכו חסום על ידי הפולינום p כך ש-xw הוא מילה בשפה L. בדרך דומה מגדירים את אוסף כל המילים x שלכל המשך w שלהן שחסום בידי p, xw שייכת לשפה:

הגדרה זו מורחבת בצורה טבעית למחלקות של שפות:

באמצעות סימונים אלו, ההיררכיה הפולינומית מוגדרת על ידי:

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

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

לא ידוע אם ההכלות הללו הן הכלות ממש או שקיים שוויון בחלק מהמקרים. לא קשה להוכיח כי אם או עבור כלשהו, אז ההיררכיה קורסת: יתקיים לכל . בפרט, אם P=NP, ההיררכיה קורסת לחלוטין וכל המחלקות בה שוות.

איחוד כל המחלקות השייכות להיררכיה הפולינומית מסומן בתור PH. ידוע כי PH מוכל במחלקה PSPACE אך לא ידוע אם קיים שוויון. מכיוון שב-PSPACE קיימות בעיות שהן PSPACE-שלמות (כדוגמת TQBF), שוויון פירושו שההיררכיה קורסת החל ממקום מסוים (כי אם קיים שוויון, הרי ש-TQBF שייכת לאיבר כלשהו בהיררכיה, ולכן החל ממנו ההיררכיה לא תוסיף לגדול).

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