PH (複雜度)和PSPACE

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

PH (複雜度)和PSPACE之间的区别

PH (複雜度) vs. PSPACE

在計算複雜度理論內，複雜度類PH代表所有在多項式譜系裡面的複雜度類聯集，亦即： PH最早是由Larry Stockmeyer定義，是一個受限交替式圖靈機(bounded alternating Turing machine)其譜系(hierarchy)的特例。這個複雜度包含於PPP(包含問題可以由多項式時間圖靈機，並且能取用PP 神諭的機器所解決的複雜度類。), P#P (根據Toda's theorem),以及PSPACE裡面。 PH有一個簡單的邏輯描述方法：PH是一個能以二階邏輯所表示語言的集合。 PH包含了幾乎所有在PSPACE裡面有名的複雜度類;舉例來說，像是P, NP，和co-NP。甚至還包含了一些概率複雜度類像是BPP和RP。然而，有一些證據指出BQP(以量子電腦可以在多項式時間之內解決的問題)並不包含在PH裡面(Aaronson 2010). PSPACE是计算复杂度理论中能被确定型图灵机利用多项式空间解决的判定问题集合，是Polynomial SPACE的简称。.

图灵机

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

PH (複雜度)和图灵机 · PSPACE和图灵机 · 查看更多 »

NP (複雜度)

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

NP (複雜度)和PH (複雜度) · NP (複雜度)和PSPACE · 查看更多 »

P (複雜度)

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

P (複雜度)和PH (複雜度) · P (複雜度)和PSPACE · 查看更多 »

PSPACE

PSPACE是计算复杂度理论中能被确定型图灵机利用多项式空间解决的判定问题集合，是Polynomial SPACE的简称。.

PH (複雜度)和PSPACE · PSPACE和PSPACE · 查看更多 »