NEXPTIME

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

以NTIME作定义

{\mbox{NEXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mbox{NTIME}}(2^{n^{k}})

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

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

参考资料

^ C. Papadimitriou. Computational Complexity Addison-Wesley, 1994. ISBN 0-201-53082-1. Section 20.1, pg.492.
^ Juris Hartmanis, Neil Immerman, Vivian Sewelson. Sparse Sets in NP-P: EXPTIME versus NEXPTIME. Information and Control, volume 65, issue 2/3, pp.158–181. 1985. At ACM Digital Library Archive.is的存档，存档日期2012-07-12

Complexity Zoo: NEXP, Complexity Zoo: coNEXP

[1] C. Papadimitriou. Computational Complexity Addison-Wesley, 1994. ISBN 0-201-53082-1. Section 20.1, pg.492.

[2] Juris Hartmanis, Neil Immerman, Vivian Sewelson. Sparse Sets in NP-P: EXPTIME versus NEXPTIME. Information and Control, volume 65, issue 2/3, pp.158–181. 1985. At ACM Digital Library Archive.is的存档，存档日期2012-07-12

[1]

[2]

NEXPTIME

相关条目

参考资料