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















