NEXPTIME是什么

Q&A 2020-10-08 00:28:05 阅读(...)

复杂性类NEXPTIME(有时称为NEXP)是一组决策问题,可以通过使用时间2n的非确定性图灵机来解决。NEXPTIME 经常出现在交互式证明系统的背景下,其中有两个主要特征。

在计算复杂性理论中,复杂性类 NEXPTIME(有时称为 NEXP)是一组决策问题,可以通过使用时间 2n 的非确定性图灵机来解决。

NEXPTIME是什么

介绍

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

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

如果P= NP,那么NEXPTIME = EXPTIME;更精确的说,ENE,若且唯若存在一个稀疏语言,在NP并且不在P里面。

替代特征

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

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

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

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

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

完整的 NEXPTIME

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

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

收藏 0个人收藏
走进科技生活方式

发表评论

登录后参与评论