徽标
联盟百科
通讯
下载应用,请到 Google Play
新! 在您的Android™设备上下载联盟百科!
自由
比浏览器更快的访问!
 

PH (複雜度)

指数 PH (複雜度)

在計算複雜度理論內,複雜度類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).

12 关系: 反NP复杂性类二階邏輯图灵机BPPBQP (複雜度)量子计算机NP (複雜度)P (複雜度)PP (複雜度)PSPACERP (複雜度)

反NP

在計算複雜度理論上,反NP類是複雜度類的其中一類。.

新!!: PH (複雜度)和反NP · 查看更多 »

复杂性类

在計算複雜度理論中,一個複雜度類指的是一群複雜度類似的問題的集合。一個典型的複雜度類的定義有以下--: 例如'''NP'''類就是一群可以被一非確定型圖靈機以多項式時間解決的決定型問題。而P類則是一群可以被確定型圖靈機以多項式時間解決的決定型問題。某些複雜度類是一群函式問題(Function problem)的集合,例如'''FP'''。 許多複雜度類可被描述它的數學邏輯(mathematical logic)特徵化,請見可描述的複雜度(descriptive complexity)。 而Blum公理用於不需實際計算模型就可定義複雜度類的情況。.

新!!: PH (複雜度)和复杂性类 · 查看更多 »

二階邏輯

在逻辑和数学中,二阶逻辑是一阶逻辑的扩展,一阶逻辑是命题逻辑的扩展。二阶逻辑接着被高阶逻辑和类型论所扩展。 一阶逻辑和二阶逻辑都使用了论域(有时叫做“域”或“全集”)的想法。论域是可以在其上量化的个体元素的集合。一阶逻辑只包括取值为论域的个体元素的变量和量词。例如在一阶句子∀x(x ≠ x + 1)中变量x被用来表示一个任意的个体。二阶逻辑扩展了一阶逻辑,通过增加取值在个体的集合上变量和量词。例如,二阶句子\forall S \forall x \Big(x \in S \vee x \notin S \Big) 声称对于所有个体的集合S和所有的个体x,要么x在S中要么不在(这是二值原理)。最一般的二阶逻辑还包括量化在函数上的变量,和在下面语法章节解说的变量。.

新!!: PH (複雜度)和二階邏輯 · 查看更多 »

图灵机

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

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

BPP

BPP(Bounded-error, Probabilistic, Polynomial time),在計算複雜性理論中的一種決定性問題 BPP 還可以指:.

新!!: PH (複雜度)和BPP · 查看更多 »

BQP (複雜度)

在計算複雜度理論內,有限錯誤量子多項式時間(bounded error quantum polynomial time,BQP)是一個決定性問題的複雜度類,並且其內的問題可以在多項式時間內以量子電腦解決,錯誤的機率小於1/3。BQP也可以視為是複雜度類BPP的量子電腦版。 換句話說,對BQP裡面的問題,存在一個使用量子電腦的演算法(量子演算法)花費多項式時間運作,並且有很高的機率回答正確的答案。對任何狀況,回答錯誤答案的機率小於三分之一。 與其他「有限錯誤」的機率演算法相同,這裡所提到的1/3是一個比較隨意的定義。如果原本演算法的錯誤機率比較大,我們可以運作多次該演算法,然後取多數回答正確的答案以取得比較高的準確率。詳細的分析顯示錯誤的下限可以高達1/2 − n−c或者低達2−nc,所包含的題目範圍均不會有變化。這裡c是一個正數的常數,n是輸入的長度。.

新!!: PH (複雜度)和BQP (複雜度) · 查看更多 »

量子计算机

量子计算机(quantum computer)是一种使用量子邏輯進行通用計算的設備。不同於电子计算机(或稱傳統電腦),量子計算用來存儲數據的對象是量子比特,它使用量子演算法來進行數據操作。马约拉纳费米子反粒子就是自己本身的属性,或许是令量子计算机的制造变成现实的一个关键。.

新!!: PH (複雜度)和量子计算机 · 查看更多 »

NP (複雜度)

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

新!!: PH (複雜度)和NP (複雜度) · 查看更多 »

P (複雜度)

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

新!!: PH (複雜度)和P (複雜度) · 查看更多 »

PP (複雜度)

在計算複雜度理論內,PP是一個複雜度類,包含可以在多項式時間裡面以概率圖靈機解決,無論輸入如何錯誤率均小於1/2的決定型問題。PP這個縮寫即代表了概率多項式時間(probabilistic polynomial time)。這個複雜度類是由Gill於1977年定義。 Lance Fortnow.

新!!: PH (複雜度)和PP (複雜度) · 查看更多 »

PSPACE

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

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

RP (複雜度)

在複雜度理論內,RP("隨機多項式時間")是一個有關機率圖靈機的複雜度類,並且存在以下特性:.

新!!: PH (複雜度)和RP (複雜度) · 查看更多 »

传出传入
嘿!我们在Facebook上吧! »