הצגת המקור של הדף "PSPACE"

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

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

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

<math>\mbox{PSPACE} = \bigcup_{k\in\mathbb{N}} \mbox{DSPACE}(n^k)</math>

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

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

== תכונות סגירות ==
המחלקה PSPACE [[סגירות (אלגברה)|סגורה]] תחת הפעולות [[איחוד (מתמטיקה)|איחוד]], [[משלים (מתמטיקה)|משלים]] ו[[כוכב קלין]]

== מיקום PSPACE בין מחלקות הסיבוכיות ==
[[קובץ:Complexity subsets pspace.svg|שמאל|ממוזער|300px|מיקום PSPACE בין מחלקות הסיבוכיות]]
פרט לשקילות ל- NPSPACE, ידועים גם היחסים הבאים בין '''PSPACE''' ומחלקות הסיבוכיות 
{{כ}} [[NL (סיבוכיות)|NL]] {{כ}}, 
{{כ}} [[P (סיבוכיות)|P]], {{כ}}
{{כ}} [[NP (סיבוכיות)|NP]], {{כ}}
{{כ}} [[EXPTIME]] {{כ}}
ו- [[EXPSPACE]]: {{כ}}

:<math>\mbox{NL} \subseteq \mbox{P} \subseteq \mbox{NP} \subseteq \mbox{PSPACE}</math>
:<math>\mbox{PSPACE} \subseteq \mbox{EXPTIME} \subseteq \mbox{EXPSPACE}</math>

יש שלושה סימוני <math>\subseteq</math> (חלקי או שקול) בשורה הראשונה, ושניים בשורה השנייה. ידוע כי בכל אחת משתי שורות אלו, לפחות אחד הסימנים צריך להיות
<math>\subsetneq</math> (כלומר קבוצה חלקית ממש ולא שקולה) אך לא ידוע איזה מהם. זאת משום שידוע כי:
:<math>\mbox{NL} \subsetneq \mbox{PSPACE} \subsetneq \mbox{EXPSPACE}</math>

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

== בעיות PSPACE-שלמות ==
בעיה B היא '''PSPACE-שלמה''' אם:
# B <math>\in</math> PSPACE, וגם:
# לכל בעיה A <math>\in</math> PSPACE מתקיים: A <math>\leq_p</math> B
כאשר A <math>\leq_p</math> B משמעו שקיימת [[רדוקציה פולינומית]] בזמן מבעיה A אל בעיה B.
בעיות '''PSPACE-שלמות''' הן הבעיות החשובות ביותר למחקר PSPACE כיוון שהן מייצגות את הבעיות הקשות ביותר במחלקה. מציאת פתרון פשוט (מבחינת זמן ריצה) לבעיה PSPACE-שלמה משמעותה מציאת פתרון פשוט לכל בעיות PSPACE כיוון שלכל בעיה ב-PSPACE יש רדוקציה פולינומית לבעיה PSPACE-שלמה.

[[קובץ:Hexposition02.jpg|שמאל|ממוזער|200px|לוח [[הקס (משחק)|הקס]]]]
הבעיה ה"קנונית" שהיא PSPACE-שלמה היא בעיית ההחלטה האם נוסחה בוליאנית עם [[כמת]]ים היא נכונה או לא. היא ידועה בראשי התבות שלה [[TQBF]] - True Quantified Boolean Formulas.

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

== ראו גם ==
* [[מחלקת סיבוכיות]]
* [[סיבוכיות מקום]]
* [[סיבוכיות זמן]]

== קישורים חיצוניים ==
*{{לא מדויק|2011/04/04/what_is_pspace/|אז מהי PSPACE?}}
* [https://web.archive.org/web/20081204124245/http://qwiki.stanford.edu/wiki/Complexity_Zoo:P#pspace PSPACE ב-Complexity Zoo]

{{מחלקות סיבוכיות}}
[[קטגוריה:מחלקות סיבוכיות]]