PSPACE和非确定型图灵机

快捷方式: 差异，相似，杰卡德相似系数，参考。

PSPACE和非确定型图灵机之间的区别

PSPACE vs. 非确定型图灵机

PSPACE是计算复杂度理论中能被确定型图灵机利用多项式空间解决的判定问题集合，是Polynomial SPACE的简称。. 如果不加特殊说明，通常所说的图灵机都是确定型图灵机。非确定型图灵机和确定型图灵机的不同之处在于，在计算的每一时刻，根据当前状态和读写头所读的符号，机器存在多种状态转移方案，机器将任意地选择其中一种方案继续运作，直到最后停机为止。具体而言，其状态转移函数为 \delta: Q \times \Gamma \to 2^ 其中Q是状态集合，\Gamma是带字母表，L, R分别表示读写头向左和向右移动；符号2^ 表示集合A的幂集，即 2^A.

图灵机

图灵机（），又称确定型图灵机，是英国数学家艾倫·图灵于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。.

PSPACE和图灵机 · 图灵机和非确定型图灵机 · 查看更多 »

NP (複雜度)

非定常多项式（non-deterministic polynomial，缩写：NP）时间复杂性类，或称非确定性多项式时间复杂性类，包含了可以在多项式时间内，对一个判定性算法问题的实例，一个给定的解是否正确的算法问题。 NP是计算复杂性理论中最重要的复杂性类之一。它包含复杂性类P，即在多项式时间内可以验证一个算法问题的实例是否有解的算法问题的集合；同时，它也包含NP完全问题，即在NP中“最难”的问题。计算复杂性理论的中心问题，P/NP问题即是判断对任意的NP完全问题，是否有有效的算法，或者NP与P是否相等。.

NP (複雜度)和PSPACE · NP (複雜度)和非确定型图灵机 · 查看更多 »

P (複雜度)

在計算複雜度理論中，P 是在複雜度類問題中可於決定性圖靈機以多項式量級（或稱多項式時間）求解的決定性問題。 P通常表示那類可以"有效率地解決"或"溫馴"的可計算型問題，就算指數級非常高也可以算作"溫馴"，例如RP與BPP問題。當然P類存在很多現實處理上一點也不溫馴的問題，例如一些至少需要n1000000指令來解決的問題。很多情況下存在著更難的複雜度問.

P (複雜度)和PSPACE · P (複雜度)和非确定型图灵机 · 查看更多 »