PSPACE

בתורת הסיבוכיות, PSPACE היא מחלקת כל בעיות ההכרעה שניתן לפתור על ידי מכונת טיורינג דטרמיניסטית תוך שימוש בסיבוכיות מקום פולינומית. במונח PSPACE, ה-P מייצגת פולינום, וה-SPACE (מקום) מייצגת את כמות המקום, כלומר הזיכרון.

המגבלה של שימוש במקום פולינומי בלבד משמעותה שעבור בעיה נתונה קיים פולינום כלשהו (P(n, כך שבהינתן קלט בגודל n, הפתרון עושה שימוש בלכל היותר (P(n מקום.

הגדרה פורמלית

ההגדרה הפורמלית של PSPACE היא:

${\mbox{PSPACE}}=\bigcup _{k\in \mathbb {N} }{\mbox{DSPACE}}(n^{k})$

כלומר איחוד כל הבעיות שניתן לפתור באופן דטרמיניסטי במקום פולינומי.

שקילות למחלקה NPSPACE

NPSPACE היא מחלקת כל בעיות ההכרעה שניתן לפתור על ידי מכונת טיורינג לא-דטרמיניסטית תוך שימוש בסיבוכיות מקום פולינומית. משפט סביץ' מוכיח שקילות בין המחלקה PSPACE למחלקה NPSPACE. כלומר כל בעיה שניתן לפתור במקום פולינומי באופן לא-דטרמיניסטי, ניתן לפתור במקום פולינומי באופן דטרמיניסטי.

תכונות סגירות

המחלקה PSPACE סגורה תחת הפעולות איחוד, משלים וכוכב קלין

מיקום PSPACE בין מחלקות הסיבוכיות

פרט לשקילות ל- NPSPACE, ידועים גם היחסים הבאים בין PSPACE ומחלקות הסיבוכיות ‏ NL ‏, ‏ P, ‏ ‏ NP, ‏ ‏ EXPTIME ‏ ו- EXPSPACE: ‏

{\mbox{NL}}\subseteq {\mbox{P}}\subseteq {\mbox{NP}}\subseteq {\mbox{PSPACE}}

{\mbox{PSPACE}}\subseteq {\mbox{EXPTIME}}\subseteq {\mbox{EXPSPACE}}

יש שלושה סימוני $\subseteq$ (חלקי או שקול) בשורה הראשונה, ושניים בשורה השנייה. ידוע כי בכל אחד משתי שורות אלו, לפחות אחד הסימנים צריך להיות $\subsetneq$ (כלומר קבוצה חלקית ממש ולא שקולה) אך לא ידוע איזה מהם. זאת משום שידוע כי:

{\mbox{NL}}\subsetneq {\mbox{PSPACE}}\subsetneq {\mbox{EXPSPACE}}

האמונה הרווחת היא כי כל ההכלות בשתי השורות למעלה הן ממשיות (כלומר כולם $\subsetneq$ ).

בעיות PSPACE-שלמות

בעיה B היא PSPACE-שלמה אם:

B $\in$ PSPACE, וגם:
לכל בעיה A $\in$ PSPACE מתקיים: A $\leq _{p}$ B

כאשר A $\leq _{p}$ B משמעו שקיימת רדוקציה פולינומית בזמן מבעיה A אל בעיה B. בעיות PSPACE-שלמות הן הבעיות החשובות ביותר למחקר PSPACE כיוון שהן מייצגות את הבעיות הקשות ביותר במחלקה. מציאת פתרון פשוט (מבחינת זמן ריצה) לבעיה PSPACE-שלמה משמעותה מציאת פתרון פשוט לכל בעיות PSPACE כיוון שלכל בעיה ב-PSPACE יש רדוקציה פולינומית לבעיה PSPACE-שלמה.

לוח הקס

הבעיה ה"קנונית" שהיא PSPACE-שלמה היא בעיית ההחלטה האם נוסחה בוליאנית עם כמתים היא נכונה או לא. היא ידועה בראשי התבות שלה TQBF - True Quantified Boolean Formulas.

סוג בעיות נוספות לגביהן ידוע שהן PSPACE-שלמות הם בעיות הקשורות למשחקים שונים כדוגמת הגרסאות המוכללות של הקס ורברסי.

ראו גם

קישורים חיצוניים

גדי אלכסנדרוביץ', אז מהי PSPACE?, באתר "לא מדויק", 4 באפריל 2011
PSPACE ב-Complexity Zoo