PSPACE
בתורת הסיבוכיות, 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?, באתר "לא מדויק", שגיאה: זמן שגוי
- 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 |
22048167PSPACE