PSPACE – הבדלי גרסאות
←שקילות למחלקה NPSPACE: המשפט לא מתייחס לסיבוכיות זמן |
|||
שורה 53: | שורה 53: | ||
== קישורים חיצוניים == |
== קישורים חיצוניים == |
||
*{{לא מדויק| |
*{{לא מדויק|2011/04/04/what_is_pspace/|אז מהי PSPACE?}} |
||
* [http://qwiki.stanford.edu/wiki/Complexity_Zoo:P#pspace PSPACE ב-Complexity Zoo] |
* [http://qwiki.stanford.edu/wiki/Complexity_Zoo:P#pspace PSPACE ב-Complexity Zoo] |
||
גרסה מ־15:27, 1 בדצמבר 2019
בתורת הסיבוכיות, PSPACE היא מחלקת כל בעיות ההכרעה שניתן לפתור על ידי מכונת טיורינג דטרמיניסטית תוך שימוש בסיבוכיות מקום פולינומית. במונח PSPACE, ה-P מייצגת פולינום, וה-SPACE (מקום) מייצגת את כמות המקום, כלומר הזיכרון.
המגבלה של שימוש במקום פולינומי בלבד משמעותה שעבור בעיה נתונה קיים פולינום כלשהו (P(n, כך שבהינתן קלט בגודל n, הפתרון עושה שימוש בלכל היותר (P(n מקום.
הגדרה פורמלית
ההגדרה הפורמלית של PSPACE היא:
כלומר איחוד כל הבעיות שניתן לפתור באופן דטרמיניסטי במקום פולינומי.
שקילות למחלקה NPSPACE
NPSPACE היא מחלקת כל בעיות ההכרעה שניתן לפתור על ידי מכונת טיורינג לא-דטרמיניסטית תוך שימוש בסיבוכיות מקום פולינומית. משפט סביץ' מוכיח שקילות בין המחלקה PSPACE למחלקה NPSPACE. כלומר כל בעיה שניתן לפתור במקום פולינומי באופן לא-דטרמיניסטי, ניתן לפתור במקום פולינומי באופן דטרמיניסטי.
תכונות סגירות
המחלקה PSPACE סגורה תחת הפעולות איחוד, משלים וכוכב קלין
מיקום PSPACE בין מחלקות הסיבוכיות
פרט לשקילות ל- NPSPACE, ידועים גם היחסים הבאים בין PSPACE ומחלקות הסיבוכיות NL , P, NP, EXPTIME ו- EXPSPACE:
יש שלושה סימוני (חלקי או שקול) בשורה הראשונה, ושניים בשורה השנייה. ידוע כי בכל אחד משתי שורות אלו, לפחות אחד הסימנים צריך להיות (כלומר קבוצה חלקית ממש ולא שקולה) אך לא ידוע איזה מהם. זאת משום שידוע כי:
האמונה הרווחת היא כי כל ההכלות בשתי השורות למעלה הן ממשיות (כלומר כולם ).
בעיות PSPACE-שלמות
בעיה B היא PSPACE-שלמה אם:
- B PSPACE, וגם:
- לכל בעיה A PSPACE מתקיים: A B
כאשר A B משמעו שקיימת רדוקציה פולינומית בזמן מבעיה A אל בעיה B. בעיות PSPACE-שלמות הן הבעיות החשובות ביותר למחקר PSPACE כיוון שהן מייצגות את הבעיות הקשות ביותר במחלקה. מציאת פתרון פשוט (מבחינת זמן ריצה) לבעיה PSPACE-שלמה משמעותה מציאת פתרון פשוט לכל בעיות PSPACE כיוון שלכל בעיה ב-PSPACE יש רדוקציה פולינומית לבעיה PSPACE-שלמה.
הבעיה ה"קנונית" שהיא PSPACE-שלמה היא בעיית ההחלטה האם נוסחה בוליאנית עם כמתים היא נכונה או לא. היא ידועה בראשי התבות שלה TQBF - True Quantified Boolean Formulas.
סוג בעיות נוספות לגביהן ידוע שהן PSPACE-שלמות הם בעיות הקשורות למשחקים שונים כדוגמת הגרסאות המוכללות של הקס ורברסי.
ראו גם
קישורים חיצוניים
- גדי אלכסנדרוביץ', אז מהי PSPACE?, באתר "לא מדויק", 4 באפריל 2011
- PSPACE ב-Complexity Zoo
מחלקות סיבוכיות חשובות (נוספות) | ||
---|---|---|
נחשב מעשי | NL • P • ZPP • RP • BPP • BQP • PTAS • APX | |
ככל הנראה בלתי מעשי | NP • NP-קשיות • co-NP • PP • #P • PSPACE | |
נחשב כבלתי מעשי | EXPTIME • NEXPTIME • EXPSPACE • ELEMENTARY • PR • R • RE • ALL | |
היררכית מחלקות | ההיררכיה הפולינומית • ההיררכיה האקספוננציאלית • ההיררכיה הבוליאנית • ההיררכיה האריתמטית • היררכית גרזגרצ'יק | |
משפחות של מחלקות | מערכת הוכחה אינטראקטיבית • DTIME • NTIME • DSPACE • NSPACE |