在计算複杂理论内，複杂度类NEXPTIME（有时叫做NEXP）是一个决定性问题的集合，包含可以使用非确定型图灵机，使用O(2)(这里的p(n)是某个多项式）的实践可以解决的问题。这里不限制空间的使用。

一个很重要的NEXPTIME-完全问题集合与简洁电路(succinct circuit)有关。简洁电路是能以指数速率缩减的空间形容图的一个机器。这个机器接收两个顶点的号码为输入，输出这两个顶点是否有边相连。如果有个问题，使用一般的图表示法，像是连线矩阵，去解决时是个NP-完全问题，那幺使用简洁电路的表示来解决这个问题是NEXPTIME-完全，因为输入的大小跟前者相比是成指数速率缩小。举个简单的例子，使用简洁电路的表示法找一张图的哈密顿图是NEXPTIME-完全。

如果P= NP，那幺NEXPTIME = EXPTIME；更精确的说，E ≠ NE，若且唯若存在一个稀疏语言，在NP并且不在P里面。

NEXPTIME经常出现在互动式证明系统的背景下，其中有两个主要特徵。第一个是MIP证明系统，其中我们有两个全能的证明器，它们与随机多项式时间验证器（但彼此不相关）进行通信。如果字元串是语言，他们必须能够以高机率说服验证者。如果字元串不在语言中，则他们必须无法协作地欺骗验证者接受字元串，除非机率很低。 MIP证明系统可以解决NEXPTIME中的每个问题这一事实令人印象深刻，当我们考虑到当只有一个证明者存在时，我们只能识别所有PSPACE;验证者“交叉检查”两个证明者的能力赋予它巨大的力量。有关详细信息，请参阅互动式校样系统#MIP。

另一种表征NEXPTIME的互动式证明系统是一类机率可检验证明。回想一下，NP可以被视为一类问题，其中一个全能的证明者给出了一个声称字元串在语言中的证明，并且确定性多项式时间机器验证它是一个有效的证明。我们对此设定进行了两处更改

1、添加随机性，翻转硬币的能力，到验证机。

2、不是简单地将声称的证据提供给磁带上的验证者，而是随机访问证明。验证者可以指定证明字元串的索引并接收相应的位。由于验证者可以写出多项式长度的索引，它可以潜在地索引到指数长的证明字元串。

这两个扩展共同极大地扩展了证明系统的功能，使其能够识别NEXPTIME中的所有语言。该类称为PCP （poly，poly）。，在该表征中，验证器可以被限制为仅读取恆定数量的比特，即NEXPTIME = PCP （poly，1）。有关详细信息，请参阅机率可检查证明。

如果它在NEXPTIME中，则决策问题是NEXPTIME-complete，并且NEXPTIME中的每个问题都具有多项式时间多次减少。换句话说，存在一种多项式时间算法，该算法将一个实例转换为具有相同答案的另一个实例。 NEXPTIME完成的问题可能被认为是NEXPTIME中最难的问题。我们知道NEXPTIME完全问题不在NP中;已经证明，这些问题不能通过时间层次定理在多项式时间内得到验证。

一组重要的NEXPTIME完整问题涉及简洁的电路。简洁的电路是用于以指数级较小的空间描述图形的简单机器。它们接受两个顶点数作为输入和输出它们之间是否存在边缘.如果在自然表示中解决图形上的问题（例如邻接矩阵）是NP完全的，那幺在简洁的电路表示上解决相同的问题是NEXPTIME完成的,因为输入指数小（在某些温和的条件下,通过“投影”实现NP完全性降低。作为一个简单的例子，为这样编码的图找到哈密顿路径是NEXPTIME完成的。