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, מחלקת הסיבוכיות של הבעיות שפתירות בזמן אקספוננציאלי על ידי מכונת טיורינג לא דטרמיניסטית.. ליתר דיוק, EXPTIME $\neq$ NEXPTIME אם"ם קיימת שפה דלילה הנמצאת ב-NP ולא ב-P.

EXPTIME שלמות

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

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

דוגמאות

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

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

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

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