指数时间EXP类(exponential time class EXP),理学-计算机科学技术-计算机科学理论-计算复杂性-复杂性类-时间复杂性类,能用指数时间(exponential time)算法求解的问题类。指数时间EXP类是确定型图灵机在指数时间内可以求解的问题类。对于长度为n的输入,指数时间图灵机的运行时间是O(),这里k>0是任意固定常数。一个语言L在指数时间EXP类中,当且仅当有一个指数时间确定型图灵机判定L。EXP类也记作EXPTIME类。EXP类包含了非确定多项式时间NP类(NP问题的穷举搜索解法花费指数时间),EXP类也包含了多项式空间PSPACE类,是否都是真包含目前还不知道。与EXP类对应的非确定指数时间类是NEXP类,EXP类包含于NEXP类,二者是否相等目前还不知道。利用padding技术,可以证明“向上塌方(collapse upward)”性质:若L=P,则PSPACE=EXP;若P=NP,则EXP=NEXP。由时间层次定理可知P≠EXP并且NP≠NEXP。EXP类有完全问题,比如在n×n棋盘上国际象棋或围棋的必胜策略问题。