NEXPTIME

编辑:夹袄网互动百科 时间:2019-12-16 02:12:36
编辑 锁定
本词条缺少概述信息栏名片图,补充相关内容使词条更完整,还能快速升级,赶紧来编辑吧!
在计算复杂理论内,复杂度类NEXPTIME(有时叫做NEXP)是一个决定性问题的集合,包含可以使用非确定型图灵机,使用O(2)(这里的p(n)是某个多项式)的实践可以解决的问题。另外这里不限制空间的使用。
一个很重要的NEXPTIME-完全问题集合与简洁电路(succinct circuit)有关。简洁电路是能以指数速率缩减的空间形容图的一个机器。这个机器接收两个顶点的号码为输入,输出这两个顶点是否有边相连。如果有个问题,使用一般的图表示法,像是连接矩阵,去解决时是个NP-完全问题,那么使用简洁电路的表示来解决这个问题是NEXPTIME-完全,因为输入的大小跟前者相比是成指数速率缩小[1]  。举个简单的例子,使用简洁电路的表示法找一张图的哈密顿图NEXPTIME-完全。
如果P= NP,那么NEXPTIME = EXPTIME;更精确的说,ENE,若且唯若存在一个稀疏语言,在NP并且不在P里面[2] 
参考资料
  • 1.    C. Papadimitriou.Computational Complexity :Addison-Wesley,1994
  • 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
词条标签:
科技