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

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

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

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

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

משפט קריסת ההיררכיה[עריכת קוד מקור | עריכה]

עבור ההיררכיה הפולינומית, מתקיים שאם , אזי . תוצאה מידית ראשונה היא שאם אזי ההיררכיה הפולינומית קורסת לדרגה 0, כלומר .

הוכחה[עריכת קוד מקור | עריכה]

נניח בלי הגבלת הכלליות ש-.

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

, כאשר לכל j חסום פולינומית וגם V מוודא פולינומי דטרמיניסטי שבודק שייכות ליחס R.

נוכיח שההיררכיה קורסת - ניתן לתאר מחלקה שקולה באופן הבא -

אבל אנחנו יודעים ש- , כלומר ניתן לתאר את היחס גם כך:

וניתן לאחד את שני המשתנים הראשונים למשתנה אחד, , ולכן מתקיים , ולכן

וכמובן מתקיים , וההוכחה הושלמה.