NEXPTIME 在計算複雜度理論內複雜度類NEXPTIME有時叫做NEXP是一個決定性問題的集合包含可以使用非確定型圖靈機使用Opn這裡的pn是某個多項式的時間可以解決的問題另外這裡不限制空間的使用 以NTIME作定義 NEXPTIME   k  N NTIME   n k  displaystyle mboxNEXPTIMEbigcup kin mathbb N mboxNTIMEnk 一個很重要的NEXPTIME完全問題集合與簡潔電路succinct circuit有關簡潔電路是能以指數速率縮減的空間形容圖的一個機器這個機器接收兩個頂點的號碼為輸入輸出這兩個頂點是否有邊相連如果有個問題使用一般的圖表示法像是連接矩陣去解決時是個NP完全問題那麼使用簡潔電路的表示來解決這個問題是NEXPTIME完全因為輸入的大小跟前者相比是成指數速率縮小舉個簡單的例子使用簡潔電路的表示法找一張圖的哈密頓圖是NEXPTIME完全 如果P  NP那麼NEXPTIME  EXPTIME更精確的說E  NE若且唯若存在一個稀疏語言在NP並且不在P裡面