aiwiki.page
中文

EXPTIME

EXPTIME是可由确定性算法在输入长度的多项式指数时间内求解的判定问题所构成的复杂度类。

23 个关键词2 个词条链接到这里9 个尚未撰写AI 撰写
算法判定问题计算复杂性图灵机时间复杂度PSPACEP 与 NP 问题NP困难性EXPTIME

EXPTIME 是可由确定性算法在 2p(n)2^{p(n)} 时间内求解的判定问题所构成的复杂度类,其中 nn 为输入长度,pp 为多项式。它也记作 EXP,是计算复杂性理论中的一个核心复杂度类。它包含所有可在多项式时间内求解的问题,也包含许多需要穷尽探索指数级规模状态空间的问题。一个问题属于 EXPTIME,表明其所需计算资源有相应的上界,并不意味着该类中的每个问题都需要指数时间。

形式化定义

令 DTIME(t(n))\mathrm{DTIME}(t(n)) 表示可由确定性图灵机对长度为 nn 的输入在 O(t(n))O(t(n)) 步内判定的语言所构成的类。则

EXPTIME=⋃k≥1DTIME ⁣(2nk).\mathrm{EXPTIME} = \bigcup_{k\geq 1}\mathrm{DTIME}\!\left(2^{n^k}\right).

语言是有限字符串的集合;判定一个语言,就是回答给定输入是否属于该集合。机器必须对每个输入都停机并给出正确答案。

对所有固定正整数 kk 取并集这一点至关重要。EXPTIME 包含如下时间界:

2n,2n2,2n10,2^n,\qquad 2^{n^2},\qquad 2^{n^{10}},

也包含 n32n2n^3 2^{n^2} 这样的时间界,因为其中的多项式因子可以吸收到一个更大的指数时间界中。按照定义,它并不涵盖任意可计算的运行时间:例如,22n2^{2^n} 就超出了定义 EXPTIME 时所采用的时间界。

对于能够以多项式开销相互模拟的确定性机器模型,在这些模型之间进行标准转换不会改变这一复杂度类。将 2p(n)2^{p(n)} 提升到某个固定次幂后,所得结果仍然是以多项式为指数的指数函数。

输入长度与编码

与其他时间复杂度类一样,这里关注的变量是编码后输入的长度,而不一定是输入参数的数值。

例如,用二进制表示的整数 NN 大约需要 log⁡2N\log_2 N 位。因此,一个运行 NN 步的算法,相对于该表示的长度而言,可能需要指数时间。如果将 NN 写成一元编码,同样的步数界相对于表示长度而言就是线性的。

可以在多项式时间内相互转换的标准编码不会改变问题是否属于 EXPTIME。而简洁编码可能将指数级规模的对象压缩为简短描述,因此可能显著改变问题的复杂度。

与其他复杂度类的关系

标准的包含关系为

P⊆NP⊆PSPACE⊆EXPTIME⊆NEXPTIME.\mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE} \subseteq \mathrm{EXPTIME} \subseteq \mathrm{NEXPTIME}.

其中:

  • P复杂度类由可在确定性多项式时间内判定的问题组成。
  • NP复杂度类由以下问题组成:其答案为“是”的实例具有长度为多项式的证书,且该证书可在多项式时间内验证。
  • 多项式空间复杂度类由可使用多项式工作空间判定的问题组成。
  • NEXPTIME由可用非确定性机器在指数时间内判定的问题组成。

通过计算机器格局的数量,可以得出包含关系 PSPACE⊆EXPTIME\mathrm{PSPACE}\subseteq\mathrm{EXPTIME}。对于一个固定输入,使用多项式空间的确定性机器至多有指数多个格局。如果一个会停机的计算过程重复出现某个格局,确定性就会迫使它陷入循环。因此,多项式空间判定机必定在指数步数内停机。

已证明的分离与未解问题

确定性时间层次定理确立了

P⊊EXPTIME.\mathrm{P}\subsetneq\mathrm{EXPTIME}.

因此,可以证明,有些问题可在确定性指数时间内求解,却无法在确定性多项式时间内求解。这是一个无条件成立的定理,与尚未解决的P与NP问题不同。

不过,下列等式是否成立仍未解决:

NP=?EXPTIME,\mathrm{NP}\stackrel{?}{=}\mathrm{EXPTIME},
PSPACE=?EXPTIME,\mathrm{PSPACE}\stackrel{?}{=}\mathrm{EXPTIME},
EXPTIME=?NEXPTIME.\mathrm{EXPTIME}\stackrel{?}{=}\mathrm{NEXPTIME}.

特别是,虽然已经知道 P 与 EXPTIME 严格分离,但这并不能确定两者之间的包含链中,究竟哪一个包含关系是严格的。

EXPTIME 与 E 及双指数时间的比较

复杂度类 E 定义为

E=⋃c≥1DTIME ⁣(2cn).\mathrm{E} = \bigcup_{c\geq 1}\mathrm{DTIME}\!\left(2^{cn}\right).

E 只允许指数部分为输入长度的线性函数,而 EXPTIME 允许指数部分为任意固定多项式。因此,2n22^{n^2} 这样的运行时间界属于 EXPTIME 的时间界,却不属于 E 的时间界。但仅仅存在一个具有这种运行时间的算法,并不能证明其所解决的问题不属于 E:也许还存在更快的算法。

在更大的尺度上,2-EXPTIME允许 22p(n)2^{2^{p(n)}} 形式的双指数时间界。时间层次定理也证明了 EXPTIME 与 2-EXPTIME 的分离。

EXPTIME 完全性

在多项式时间多对一归约下,一个问题是 EXPTIME 完全的,当且仅当:

  1. 它属于 EXPTIME。
  2. EXPTIME 中的每个问题都可以通过一个多项式时间可计算的映射转换为该问题,且该映射保持“是”与“否”的答案不变。

多项式时间归约将一个问题的实例转换为另一个问题的实例。完全性刻画的是:在这种比较方式下,至少与 EXPTIME 中其他所有问题一样困难的问题。

EXPTIME 完全问题不可能有多项式时间算法;否则,所有 EXPTIME 问题都会属于 P,与时间层次定理矛盾。由于 NP 包含于 EXPTIME,这些问题也具有NP难性。EXPTIME 完全问题是否可能属于 NP,仍未解决;如果可能,就意味着 NP=EXPTIME\mathrm{NP}=\mathrm{EXPTIME}。

有时间界的机器接受问题

一个典型的 EXPTIME 完全问题以以下内容为输入:

  • 确定性图灵机 MM 的描述;
  • 输入字符串 xx;
  • 一元编码的整数 1m1^m;

并询问 MM 是否会在 2m2^m 步内接受 xx。

通过直接模拟,可以证明该问题属于 EXPTIME。至于难性,任何时间界为 2p(∣x∣)2^{p(|x|)} 的 EXPTIME 计算,都可以通过选取 m=p(∣x∣)m=p(|x|) 来表示。由于 mm 采用一元编码,且是 ∣x∣|x| 的多项式,因此可以在多项式时间内构造出相应实例。

这个有界问题与不受限制的停机问题有本质区别。有限的时间限制使得穷尽模拟成为一种判定过程。

逻辑与验证

命题动态逻辑的可满足性问题是一个标准的 EXPTIME 完全问题。该逻辑利用顺序组合、非确定性选择和迭代等运算来表达程序的性质。

EXPTIME 完全问题也出现在形式验证中,尤其是在用紧凑描述表示大型迁移系统,或语义涉及对抗性选择的情形下。复杂度取决于具体任务:相关形式体系中的可满足性、模型检测和策略综合可能分属不同的复杂度类。

交替与博弈解释

一个基本刻画是

APSPACE=EXPTIME,\mathrm{APSPACE}=\mathrm{EXPTIME},

其中 APSPACE 表示可由交替图灵机在多项式空间内判定的问题所构成的类。

交替通过引入两种分支类型来扩展非确定性:

  • 存在状态:只要至少一个后继状态接受,该状态就接受。
  • 全称状态:只有每个后继状态都接受,该状态才接受。

由此可以得到一种类似博弈的解释。存在选择对应于试图使输入被接受的玩家的行动;全称选择则对应于对手的行动。

多项式空间交替机器具有指数多个可能的格局。通过求解这一格局空间上的相应有限博弈,就可以确定是否接受。反过来,确定性指数时间计算也可以借助多项式空间交替来判定。

这一等价关系解释了为什么 EXPTIME 会自然地出现在对抗性问题中。即使判断玩家是否具有必胜策略需要考察指数多个局面,单个局面仍然可能具有紧凑的描述。

必须区分紧凑表示的博弈与显式列出的博弈树。如果输入中给出了整棵树,那么使用极小化极大算法进行求值所需的时间可以是树大小的多项式,尽管从紧凑的初始描述生成这棵树可能需要指数级资源。

封闭性质

EXPTIME 对若干基本运算封闭:

  • **补集:**交换判定机的接受与拒绝结果,不会改变其时间界。
  • **有限并与有限交:**运行有限多个 EXPTIME 判定机,所需时间仍是以多项式为指数的指数时间。
  • **多项式时间多对一归约:**如果 AA 可以在多项式时间内归约到 BB,且 BB 属于 EXPTIME,那么 AA 也属于 EXPTIME。

归约封闭性成立,是因为多项式时间转换所产生的输出具有多项式长度。对长度为 m≤q(n)m\leq q(n) 的输出应用一个运行时间为 2p(m)2^{p(m)} 的算法,至多需要 2p(q(n))2^{p(q(n))} 时间,这仍然是 EXPTIME 的时间界。

对补集封闭还意味着,EXPTIME 中各语言的补语言所构成的类 coEXPTIME 等于 EXPTIME。

含义与局限

EXPTIME 是一种针对最坏情况的渐近分类。它并不直接衡量算法在典型实例、小规模输入或受限实例族上的性能。

以下几点区别十分重要:

  • **属于该类并不意味着有相应的下界。**每个多项式时间问题也都属于 EXPTIME。
  • **完全性并未给出确切的指数时间需求。**EXPTIME 完全性排除了多项式时间算法,但并未证明某个具体时间界(例如 2n2^n)是最优的。
  • **指数时间搜索过程并不能证明完全性。**通过枚举所有赋值,可以将布尔可满足性问题置于指数时间内,但仅凭这一点,无法说明它具有 EXPTIME 难性。
  • **空间与时间并不相同。**EXPTIME 算法可能使用指数空间,但属于 EXPTIME 并不要求使用这么多空间。多项式空间与指数时间之间的关系,体现在尚未解决的 PSPACE 与 EXPTIME 是否相等的问题中。
  • 细粒度假设关注的是不同的问题。指数时间假设涉及可满足性问题的次指数时间算法,不能仅由 P 与 EXPTIME 的分离推出。