EXPTIME

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
שרטוט סכמתי של היררכיית מחלקות הסיבוכיות

בתורת הסיבוכיות, מחלקת הסיבוכיות EXPTIME (נקראת גם EXP או DEXPTIME) היא קבוצת כל בעיות ההכרעה הניתנות לפתרון באמצעות מכונת טיורינג דטרמיניסטית בזמן O(2^{p(n)}) כאשר O הוא סימון אסימפטוטי וp(n) הוא פולינום.

ניתן גם להגדיר את EXPTIME בצורה הבאה:

\mbox{EXPTIME} = \bigcup_{k \in \mathbb{N} } \mbox{ DTIME } \left( 2^{ n^k } \right)

מבחינת היררכיית מחלקות הסיבוכיות בזמן ובמקום, ידוע כי מתקיים:

P \subseteq NP \subseteq PSPACE \subseteq EXPTIME \subseteq NEXPTIME \subseteq EXPSPACE

וכמו כן, ידוע ממשפט ההיררכיה בזמן(אנ') וממשפט ההיררכיה במקום (אנ') כי:

P \subsetneq EXPTIME and NP \subsetneq NEXPTIME and PSPACE \subsetneq EXPSPACE

כך שלפחות אחת משלוש ההכלות הראשונות ואחת משלוש ההכלות האחרונות צריכה להיות הכלה של ממש, אך לא ידוע על אחת כזו. רוב המומחים מאמינים שכל ההכלות הן הכלות של ממש. כמו כן, אם P=NP, אזי EXPTIME=NEXPTIME, מחלקת הסיבוכיות של הבעיות שפתירות בזמן אקספוננציאלי על ידי מכונת טיורינג לא דטרמיניסטית. [1]. ליתר דיוק, EXPTIME  \neq NEXPTIME אם"ם קיימת שפה דלילה [2] הנמצאת ב-NP ולא ב-P [3].

EXPTIME שלמות[עריכת קוד מקור | עריכה]

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

אחת הבעיות הלא כריעות החשובות בתורת הסיבוכיות היא בעיית העצירה. גרסה יותר בסיסית של בעיה זו היא האם מכונת טיורינג דטרמיניסטית עוצרת על מילת קלט תוך לכל היותר k צעדים. בעיה זו שייכת ל-EXPTIME כיוון שהרצה טריויאלית של המכונה דורשת זמן ריצה של O(k), כאשר k מקודד בlog(k) ביטים [4]. היא EXPTIME-שלמה כיוון שניתן להשתמש בה כדי להכריע האם מכונת טיורינג שפותרת בעיה ב-EXPTIME מקבלת את הקלט שלה בכמות אקספוננציאלית של צעדים. בעיה זו כשנכתבת בבסיס אונרי היא P-שלמה.

דוגמאות[עריכת קוד מקור | עריכה]

דוגמאות נוספות לבעיות EXPTIME-שלמות ניתן למצוא במשחקים מוכללים, כגון:

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

דוגמה נוספת לבעיות EXPTIME-שלמות הן מעגלים תמציתיים. מעגלים תמציתיים הם מכונות פשוטות שמשמשות לתיאור של גרפים במקום קטן מאקספוננציאלי. הם מקבלים 2 מספרים של קודקודים בגרף כקלט, ופולטים האם יש צלע ביניהם בגרף. בעבור הרבה בעיות גרפים P-שלמות בהן הגרף מיוצג באמצעות מטריצת שכנות, פתרון אותה הבעיה עם מעגל תמציתי זו בעיה EXPTIME-שלמה, היות שהקלט קטן אקספוננציאלית. [8]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Christos Papadimitriou (1994). Computational Complexity. Addison-Wesley. ISBN 0-201-53082-1.  Section 20.1, page 491.
  2. ^ שפה דלילה היא שפה שקיים עבורה פולינום f, כך שכמות המילים בשפה באורך n חסום על ידי f(n)
  3. ^ Juris Hartmanis, Neil Immerman, Vivian Sewelson. Sparse Sets in NP-P: EXPTIME versus NEXPTIME. Information and Control, volume 65, issue 2/3, pp.158–181. 1985. At ACM Digital Library
  4. ^ Chris Umans. CS 21: Lecture 18 notes. Slide 10.
  5. ^ Aviezri Fraenkel and D. Lichtenstein (1981). "Computing a perfect strategy for n×n chess requires time exponential in n". J. Comb. Th. A (31): 199–214. 
  6. ^ J. M. Robson (1984). "N by N checkers is Exptime complete". SIAM Journal on Computing 13 (2): 252–267. doi:10.1137/0213018. 
  7. ^ J. M. Robson (1983). “The complexity of Go”, Information Processing; Proceedings of IFIP Congress, 413–417. 
  8. ^ Papadimitriou (1994), section 20.1, page 492.