כל מה שרצית לדעת על EXPTIME:
בתורת הסיבוכיות, מחלקת הסיבוכיות EXPTIME (נקראת גם EXP או DEXPTIME) היא קבוצת כל בעיות ההכרעה הניתנות לפתרון באמצעות מכונת טיורינג דטרמיניסטית בזמן O ( 2 p ( n ) ) {\displaystyle O(2^{p(n)})} כאשר O {\displaystyle O} הוא סימון אסימפטוטי ו p ( n ) {\displaystyle p(n)} הוא פולינום.
ניתן גם להגדיר את EXPTIME בצורה הבאה: EXPTIME = ⋃ k ∈ N DTIME ( 2 n k ) {\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, מחלקת הסיבוכיות של הבעיות שפתירות בזמן אקספוננציאלי על ידי מכונת טיורינג לא דטרמיניסטית.
.
ליתר דיוק, EXPTIME ≠ {\displaystyle \neq } NEXPTIME אם"ם קיימת שפה דלילה הנמצאת ב-NP ולא ב-P.