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

[[קובץ:Complexity subsets pspace.svg|ממוזער|300px|שרטוט סכמתי של היררכיית מחלקות הסיבוכיות]]
ב[[תורת הסיבוכיות]], [[מחלקת סיבוכיות|מחלקת הסיבוכיות]] '''EXPTIME''' (נקראת גם '''EXP''' או '''DEXPTIME''') היא [[קבוצה (מתמטיקה)|קבוצת]] כל [[בעיית הכרעה|בעיות ההכרעה]] הניתנות לפתרון באמצעות [[מכונת טיורינג]] דטרמיניסטית  בזמן <math>O(2^{p(n)})</math> כאשר <math>O</math> הוא [[סימון אסימפטוטי]] ו<math>p(n)</math> הוא פולינום.

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

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

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

:[[P (מחלקת סיבוכיות)|P]] <math>\subseteq</math> [[NP (מחלקת סיבוכיות)|NP]] <math>\subseteq</math> [[PSPACE]] <math>\subseteq</math> EXPTIME <math>\subseteq</math> [[NEXPTIME]] <math>\subseteq</math> [[EXPSPACE]]

וכמו כן, ידוע מ[[משפט ההיררכיה בזמן]]{{אנ|Time hierarchy theorem}} ומ[[משפט ההיררכיה במקום]] {{אנ|Space hierarchy theorem}} כי:

P <math>\subsetneq</math> EXPTIME   ''and''   NP <math>\subsetneq</math> NEXPTIME   ''and''   PSPACE <math>\subsetneq</math> EXPSPACE

כך שלפחות אחת משלוש ההכלות הראשונות ואחת משלוש ההכלות האחרונות צריכה להיות הכלה של ממש, אך לא ידוע על אחת כזו. רוב המומחים מאמינים שכל ההכלות הן הכלות של ממש. כמו כן, אם [[NP (מחלקת סיבוכיות)#שאלת P=NP|P=NP]], אזי EXPTIME=NEXPTIME, מחלקת הסיבוכיות של הבעיות שפתירות בזמן אקספוננציאלי על ידי [[מכונת טיורינג לא-דטרמיניסטית|מכונת טיורינג לא דטרמיניסטית]].{{הערה|{{cite book| author = Christos Papadimitriou| title = Computational Complexity| publisher = Addison-Wesley| year = 1994| isbn = 0-201-53082-1| authorlink = Christos Papadimitriou}} Section 20.1, page 491.}}. ליתר דיוק, '''EXPTIME <math> \neq </math> NEXPTIME''' [[אם"ם]] קיימת [[שפה פורמלית|שפה]] דלילה{{הערה| שפה דלילה היא שפה שקיים עבורה פולינום f, כך שכמות המילים בשפה באורך n חסום על ידי f(n) }} הנמצאת ב-'''NP''' ולא ב-'''P'''{{הערה|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. [http://portal.acm.org/citation.cfm?id=808769 At ACM Digital Library]}}.

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

אחת הבעיות הלא [[כריעות]] החשובות בתורת הסיבוכיות היא [[בעיית העצירה]]. גרסה יותר בסיסית של בעיה זו היא האם מכונת טיורינג דטרמיניסטית עוצרת על מילת [[קלט]] תוך לכל היותר k צעדים. בעיה זו שייכת ל-EXPTIME כיוון שהרצה טריוויאלית של המכונה דורשת זמן ריצה של <math>O(k)</math>, כאשר k מקודד ב<math>log(k)</math> ביטים{{הערה|
{{cite web| author = Chris Umans| url = http://www.cs.caltech.edu/~umans/cs21/lec18.pdf| title = CS 21: Lecture 18 notes| access-date = 2014-06-30| archive-date = 2010-07-20| archive-url = https://web.archive.org/web/20100720135036/http://www.cs.caltech.edu/%7Eumans/cs21/lec18.pdf|url-status=dead}} Slide 10.}}. היא EXPTIME-שלמה כיוון שניתן להשתמש בה כדי להכריע האם מכונת טיורינג שפותרת בעיה ב-EXPTIME מקבלת את הקלט שלה בכמות אקספוננציאלית של צעדים. בעיה זו כשנכתבת בבסיס אונרי היא P-שלמה.

==דוגמאות==
דוגמאות נוספות לבעיות EXPTIME-שלמות ניתן למצוא במשחקים מוכללים, כגון:
* [[שחמט]] (בעיה בה ניתן לשחק שחמט על לוח בגודל n על n, עם 2n כלי משחק לכל שחקן){{הערה|שם=Fraenkel1981|{{cite journal| author = [[Aviezri Fraenkel]] and D. Lichtenstein| title = Computing a perfect strategy for n&times;n chess requires time exponential in n| journal = J. Comb. Th. A| issue = 31| year = 1981| pages = 199–214}}}}.
* [[דמקה]]{{הערה|שם=robson1984|{{cite journal| author = J. M. Robson| title = N by N checkers is Exptime complete| journal = SIAM Journal on Computing| volume = 13| issue = 2| pages = 252–267| year = 1984| doi = 10.1137/0213018}}}}.
* [[גו (משחק)|גו]] (עם חוקי ''קו'' [[יפן|יפניים]]){{הערה|{{Cite book| author = J. M. Robson| chapter = The complexity of Go| title = Information Processing; Proceedings of IFIP Congress| year = 1983| pages = 413–417}}}}.

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

דוגמה נוספת לבעיות EXPTIME-שלמות הן ''מעגלים תמציתיים''. מעגלים תמציתיים הם מכונות פשוטות שמשמשות לתיאור של גרפים במקום קטן מאקספוננציאלי. הם מקבלים 2 מספרים של קודקודים בגרף כקלט, ופולטים האם יש צלע ביניהם בגרף. בעבור הרבה בעיות גרפים P-שלמות בהן הגרף מיוצג באמצעות [[מטריצת שכנות]], פתרון אותה הבעיה עם מעגל תמציתי זו בעיה EXPTIME-שלמה, היות שהקלט קטן אקספוננציאלית.{{הערה|Papadimitriou (1994), section 20.1, page 492.}}

==הערות שוליים==
{{הערות שוליים}}

{{מחלקות סיבוכיות}}

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