EXPTIME

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

שרטוט סכמתי של היררכיית מחלקות הסיבוכיות

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

${\displaystyle {\mbox{EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{ DTIME }}\left(2^{n^{k}}\right)}$

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

P ${\displaystyle \subseteq }$ NP ${\displaystyle \subseteq }$ PSPACE ${\displaystyle \subseteq }$ EXPTIME ${\displaystyle \subseteq }$ NEXPTIME ${\displaystyle \subseteq }$ EXPSPACE

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

P ${\displaystyle \subsetneq }$ EXPTIME and NP ${\displaystyle \subsetneq }$ NEXPTIME and PSPACE ${\displaystyle \subsetneq }$ EXPSPACE

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

EXPTIME שלמות

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

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

דוגמאות

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

• שחמט (בעיה בה ניתן לשחק שחמט על לוח בגודל n על n, עם 2n כלי משחק לכל שחקן)^[5].
• דמקה^[6].
• גו (עם חוקי קו יפניים)^[7].

קל לראות כי משחקים אלה הם ב-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" (PDF). אורכב מ-המקור (PDF) ב-2010-07-20. נבדק ב-2014-06-30. 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. pp. 413–417.
8. Papadimitriou (1994), section 20.1, page 492.