Loading AI tools
מוויקיפדיה, האנציקלופדיה החופשית
בתורת הסיבוכיות, PSPACE היא מחלקת כל בעיות ההכרעה שניתן לפתור על ידי מכונת טיורינג דטרמיניסטית תוך שימוש בסיבוכיות מקום פולינומית. במונח PSPACE, ה-P מייצגת פולינום, וה-SPACE (מקום) מייצגת את כמות המקום, כלומר הזיכרון.
המגבלה של שימוש במקום פולינומי בלבד משמעותה שעבור בעיה נתונה קיים פולינום כלשהו (P(n, כך שבהינתן קלט בגודל n, הפתרון עושה שימוש בלכל היותר (P(n מקום.
ההגדרה הפורמלית של PSPACE היא:
כלומר איחוד כל הבעיות שניתן לפתור באופן דטרמיניסטי במקום פולינומי.
NPSPACE היא מחלקת כל בעיות ההכרעה שניתן לפתור על ידי מכונת טיורינג לא-דטרמיניסטית תוך שימוש בסיבוכיות מקום פולינומית. משפט סביץ' מוכיח שקילות בין המחלקה PSPACE למחלקה NPSPACE. כלומר כל בעיה שניתן לפתור במקום פולינומי באופן לא-דטרמיניסטי, ניתן לפתור במקום פולינומי באופן דטרמיניסטי.
פרט לשקילות ל- NPSPACE, ידועים גם היחסים הבאים בין PSPACE ומחלקות הסיבוכיות NL , P, NP, EXPTIME ו- EXPSPACE:
יש שלושה סימוני (חלקי או שקול) בשורה הראשונה, ושניים בשורה השנייה. ידוע כי בכל אחד משתי שורות אלו, לפחות אחד הסימנים צריך להיות (כלומר קבוצה חלקית ממש ולא שקולה) אך לא ידוע איזה מהם. זאת משום שידוע כי:
האמונה הרווחת היא כי כל ההכלות בשתי השורות למעלה הן ממשיות (כלומר כולם ).
בעיה B היא PSPACE-שלמה אם:
כאשר A B משמעו שקיימת רדוקציה פולינומית בזמן מבעיה A אל בעיה B. בעיות PSPACE-שלמות הן הבעיות החשובות ביותר למחקר PSPACE כיוון שהן מייצגות את הבעיות הקשות ביותר במחלקה. מציאת פתרון פשוט (מבחינת זמן ריצה) לבעיה PSPACE-שלמה משמעותה מציאת פתרון פשוט לכל בעיות PSPACE כיוון שלכל בעיה ב-PSPACE יש רדוקציה פולינומית לבעיה PSPACE-שלמה.
הבעיה ה"קנונית" שהיא PSPACE-שלמה היא בעיית ההחלטה האם נוסחה בוליאנית עם כמתים היא נכונה או לא. היא ידועה בראשי התבות שלה TQBF - True Quantified Boolean Formulas.
סוג בעיות נוספות לגביהן ידוע שהן PSPACE-שלמות הם בעיות הקשורות למשחקים שונים כדוגמת הגרסאות המוכללות של הקס ורברסי.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.