ในทฤษฎีความซับซ้อนของการคำนวณคลาสความซับซ้อนEXPTIME (บางครั้งเรียกว่าEXPหรือDEXPTIME ) คือเซตของปัญหาการตัดสินใจ ทั้งหมด ที่สามารถแก้ไขได้โดยเครื่องจักรทัวริงแบบกำหนดได้ ในเวลาเลขชี้กำลัง กล่าวคือ ใน เวลา O (2p ^{( n ) )}โดยที่p ( n ) เป็นฟังก์ชันพหุนามของ n

EXPTIME เป็นคลาสที่เข้าใจง่ายคลาสหนึ่งในลำดับชั้นความซับซ้อนแบบเลขชี้กำลัง ซึ่งมีออราเคิลหรือตัวบ่งปริมาณที่ซับซ้อนขึ้นเรื่อยๆ ตัวอย่างเช่น คลาส2-EXPTIMEถูกกำหนดในลักษณะเดียวกับ EXPTIME แต่มี ขอบเขตเวลา แบบเลขชี้กำลังสองเท่าซึ่งสามารถขยายไปสู่ขอบเขตเวลาที่สูงขึ้นเรื่อยๆ ได้

EXPTIME สามารถเขียนใหม่ได้เป็นคลาสพื้นที่ APSPACE ซึ่งเป็นเซตของปัญหาทั้งหมดที่สามารถแก้ไขได้โดยเครื่องทัวริงแบบสลับในปริภูมิพหุนาม

EXPTIME มีความสัมพันธ์กับคลาสความซับซ้อนของเวลาและพื้นที่พื้นฐานอื่นๆ ในลักษณะดังต่อไปนี้: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACEนอกจากนี้ จากทฤษฎีบทลำดับชั้นของเวลาและทฤษฎีบทลำดับชั้นของพื้นที่ทำให้ทราบว่า P ⊊ EXPTIME, NP ⊊ NEXPTIME และ PSPACE ⊊ EXPSPACE

ในแง่ของDTIMEนั้น

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

เป็นที่ทราบกันว่า

และนอกจากนี้ โดยทฤษฎีลำดับชั้นของเวลาและทฤษฎีลำดับชั้นของพื้นที่นั้น

ในนิพจน์ข้างต้น สัญลักษณ์ ⊆ หมายถึง "เป็นเซตย่อยของ" และสัญลักษณ์ ⊊ หมายถึง "เป็นเซตย่อยที่แน่นอนของ"

ดังนั้นอย่างน้อยหนึ่งในสามการรวมแรกและอย่างน้อยหนึ่งในสามการรวมสุดท้ายจะต้องเป็นการรวมที่เหมาะสม แต่ไม่ทราบว่าการรวมใดบ้าง นอกจากนี้ยังทราบด้วยว่าถ้าP = NPแล้ว EXPTIME = NEXPTIMEซึ่งเป็นคลาสของปัญหาที่สามารถแก้ไขได้ในเวลาเลขชี้กำลังโดย เครื่องจักรทัวริ งแบบไม่กำหนด^{[ 1 ] กล่าว}ให้แม่นยำยิ่งขึ้นE ≠ NEก็ต่อเมื่อมีภาษาเบาบางในNPที่ไม่ได้อยู่ในP [ ^{2 ]}

EXPTIME สามารถกำหนดใหม่ได้เป็นคลาสพื้นที่ APSPACE ซึ่งเป็นเซตของปัญหาทั้งหมดที่สามารถแก้ไขได้โดยเครื่องทัวริงแบบสลับในพื้นที่พหุนาม นี่เป็นวิธีหนึ่งที่จะเห็นว่า PSPACE ⊆ EXPTIME เนื่องจากเครื่องทัวริงแบบสลับมีประสิทธิภาพอย่างน้อยเท่ากับเครื่องทัวริงแบบกำหนด^{[ 3 ]}

ปัญหาการตัดสินใจเรียกว่า EXPTIME-complete ถ้าปัญหานั้นอยู่ใน EXPTIME และทุกปัญหาใน EXPTIME สามารถลดรูป many-one ในเวลาพหุนามได้ กล่าวอีกนัยหนึ่งคือ มีอัลกอริทึม ในเวลาพหุนาม ที่แปลงอินสแตนซ์ของปัญหาหนึ่งไปเป็นอินสแตนซ์ของอีกปัญหาหนึ่งโดยให้คำตอบเดียวกัน ปัญหาที่เป็น EXPTIME-complete อาจถูกมองว่าเป็นปัญหาที่ยากที่สุดใน EXPTIME โปรดสังเกตว่าถึงแม้จะไม่ทราบว่า NP เท่ากับ P หรือไม่ แต่เรารู้ว่าปัญหา EXPTIME-complete ไม่ได้อยู่ใน P; มีการพิสูจน์แล้วว่าปัญหาเหล่านี้ไม่สามารถแก้ไขได้ในเวลาพหุนามโดย ทฤษฎีบทลำดับชั้น ของ เวลา

ในทฤษฎีความสามารถในการคำนวณปัญหาที่ไม่สามารถตัดสินได้พื้นฐานอย่างหนึ่งคือปัญหาการหยุดทำงาน : การตัดสินใจว่าเครื่องจักรทัวริงแบบกำหนด (DTM) หยุดทำงานหรือไม่ หนึ่งในปัญหาที่สมบูรณ์แบบ EXPTIME ที่สำคัญที่สุดคือเวอร์ชันที่ง่ายกว่านี้ ซึ่งถามว่า DTM หยุดทำงานบนอินพุตที่กำหนดภายในขั้นตอนไม่เกินkหรือไม่ ปัญหานี้อยู่ใน EXPTIME เพราะการจำลองแบบง่ายๆ ต้องใช้เวลา O( k ) และอินพุตkถูกเข้ารหัสโดยใช้บิต O(log k ) ซึ่งทำให้จำนวนการจำลองเป็นแบบเลขชี้กำลัง ปัญหานี้สมบูรณ์แบบ EXPTIME เพราะโดยคร่าวๆ แล้ว เราสามารถใช้มันเพื่อตรวจสอบว่าเครื่องจักรที่แก้ปัญหา EXPTIME ยอมรับในจำนวนขั้นตอนแบบเลขชี้กำลังหรือไม่ มันจะไม่ใช้มากกว่านี้^{[ 4 ]}ปัญหาเดียวกันนี้ที่มีจำนวนขั้นตอนที่เขียนในรูปแบบเอกภาคคือP- complete

ตัวอย่างอื่นๆ ของปัญหา EXPTIME-complete ได้แก่ ปัญหาการประเมินตำแหน่งใน^{หมากรุกทั่วไป [ 5 ] หมากฮอส [ 6 ] หรือโกะ (ด้วยกฎ ko ของญี่ปุ่น) [ 7} ] เกมเหล่า^{นี้มีโอกาส}ที่จะ^{เป็นEXPTIME} - completeเพราะ^{เกมสามารถดำเนิน}ไปได้จำนวนตาเดินที่เป็นเลขชี้กำลังตามขนาดของกระดาน ในตัวอย่างโกะ กฎ ko ของญี่ปุ่นเป็นที่ทราบกันดีว่าหมายถึง EXPTIME-complete แต่ไม่ทราบว่ากฎของอเมริกาหรือจีนสำหรับเกมนี้เป็น EXPTIME-complete หรือไม่ (อาจมีตั้งแต่ PSPACE ถึง EXPSPACE)

ในทางตรงกันข้าม เกมทั่วไปที่สามารถเล่นได้เป็นจำนวนตาเดินที่เป็นพหุนามตามขนาดของกระดาน มักจะเป็นเกมที่สมบูรณ์แบบ PSPACEเช่นเดียวกับเกมที่มีความยาวแบบเลขชี้กำลังซึ่งการไม่ซ้ำกันเป็นไปโดยอัตโนมัติ

ปัญหาสำคัญอีกชุดหนึ่งที่เทียบเท่ากับปัญหา EXPTIME-complete เกี่ยวข้องกับวงจรแบบกระชับ แนวคิดก็คือ ถ้าเราสามารถบีบอัดคำอธิบายของปัญหาที่ต้องใช้เวลาแบบพหุนามได้ในระดับเลขชี้กำลัง ปัญหาที่ถูกบีบอัดนั้นก็จะใช้เวลาแบบเลขชี้กำลังเช่นกัน

ยกตัวอย่างเช่น กราฟบางประเภทสามารถอธิบายได้อย่างกระชับด้วยวงจรบูลีนขนาดเล็ก วงจรนี้มีอินพุต เอาต์พุต 1 ตัว และเกต จึงต้องใช้บิตในการอธิบาย วงจรนี้แทนกราฟที่มีจุดยอด สำหรับแต่ละคู่ของจุดยอด หากป้อนรหัสไบนารีของจุดยอดทั้งสองเข้าไปในวงจร เอาต์พุตของวงจรจะระบุว่าจุดยอดทั้งสองเชื่อมต่อกันด้วยเส้นขอบหรือไม่ ${\displaystyle 2n}$${\displaystyle {\mathsf {poly}}(n)}$${\displaystyle {\mathsf {poly}}(n)}$${\displaystyle 2^{n}}$

สำหรับ ปัญหาการตัดสินใจ P-complete ที่เกิดขึ้นตามธรรมชาติจำนวนมาก เกี่ยวกับกราฟ ซึ่งกราฟแสดงในรูปแบบที่เป็นธรรมชาติ เช่นเมทริกซ์ประชิดการแก้ปัญหาเดียวกันบนการแสดงวงจรแบบกระชับนั้นสมบูรณ์แบบ EXPTIME เนื่องจากอินพุตมีขนาดเล็กกว่าแบบเลขชี้กำลัง แต่สิ่งนี้ต้องใช้การพิสูจน์ที่ไม่ธรรมดา เนื่องจากวงจรแบบกระชับสามารถอธิบายได้เฉพาะกราฟย่อยเท่านั้น^{[ 8 ]}

โดยทั่วไป วงจรบูลีนที่มีอินพุตและเอาต์พุตเดียวเป็นการแสดงแบบกระชับของสตริงของบิต ซึ่งสามารถใช้เพื่ออธิบายวัตถุอื่น เช่น กราฟสูตร 3-CNFเป็นต้น สำหรับปัญหา NP-complete ที่รู้จักเกือบทั้งหมด เวอร์ชันแบบกระชับของมันคือ NEXP-complete โดยเฉพาะอย่างยิ่ง SUCCINCT 3-SAT คือ NEXP-complete ภายใต้การลดเวลาพหุนาม^{[ 9 ] [ 10 ]}${\displaystyle n}$${\displaystyle 2^{n}}$