跳转到内容

2-EXPTIME

维基百科,自由的百科全书

计算复杂度理论内,2-EXPTIME这个复杂度类 (有时写作2-EXP)是在O(22p(n))时间内,可以使用决定型图灵机解决掉决定型问题的集合,这里 p(n) 是n的一个多项式

DTIME的方式说明,

我们已经知道

P NP PSPACE EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY.

2-EXPTIME也可以被重构成AEXPSPACE这个空间复杂度类(使用交替式图灵机可以在指数空间内解决的问题)。因为交替式图灵机至少有跟决定型图灵机一样的计算力,所以这也是一个看出EXPSPACE 2-EXPTIME的方式。[1]

2-EXPTIME这个复杂度类,是在一种可以不断提升时间上限的复杂度类层级里面的其中一类。像3-EXPTIME 这个类别,类似于2-EXPTIME的定义方式,可以用三倍指数时间限制 来定义。用同样的方法可以定义出更高的时间上限(4-EXP,5-EXP…之类)。

2-EXPTIME-完全问题

许多一般化之后全部资讯可观察的游戏(fully observable games)是EXPTIME-完全问题。

一般化的部份资讯可观察游戏(partially observable problems)相较于全部资讯可观察的游戏,其困难度则从EXPTIME-完全问题变成了2-EXPTIME-完全问题。[2]

相关页面

参考资料

  1. ^ Christos Papadimitriou, Computational Complexity (1994), ISBN 9780201530827. Section 20.1, corollary 3, page 495.
  2. ^ Jussi Rintanen. Complexity of Planning with Partial Observability. Proceedings of International Conference on Automated Planning and Scheduling (AAAI Press). 2004: 345–354.