BPP (複雜度)和P (複雜度)

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

BPP (複雜度)和P (複雜度)之间的区别

BPP (複雜度) vs. P (複雜度)

在計算複雜度理論裡面，BPP是在多項式時間內以概率圖靈機解出的問題的集合, 並且對所有的輸入，輸出結果有錯誤的概率在1/3之內。BPP這個簡寫代表"Bounded-error"(有限錯誤)，"Probabilistic"(機率的)，"Polynomial time"(多項式時間)。 要是一個問題在BPP集合裡面，則存在一個演算法，此演算法允許轉硬幣作隨機的決定，並在多項式時間內結束。 對這個演算法的任何輸入，他都要在小於1/3的錯誤概率之下給出正確判斷，不論這一個問題的答案是"正確"或者"錯誤"。 在這裡定義裡面的1/3是任意給定的。它可以是在 0 與 1/2(不包含0與1/2自身) 之間的 任意常數而BPP集合維持不變(當然這個常數必須跟輸入值為何無關)。原因在於，雖然這演算法有錯誤的機率，但是只要我們多進行幾次演算法，那多數的答案都是錯誤的機率會呈現指數衰減. 在計算複雜度理論中，P 是在複雜度類問題中可於決定性圖靈機以多項式量級（或稱多項式時間）求解的決定性問題。 P通常表示那類可以"有效率地解決"或"溫馴"的可計算型問題，就算指數級非常高也可以算作"溫馴"，例如RP與BPP問題。當然P類存在很多現實處理上一點也不溫馴的問題，例如一些至少需要n1000000指令來解決的問題。很多情況下存在著更難的複雜度問.

多項式時間

多項式時間（Polynomial time）在計算複雜度理論中，指的是一個問題的計算時間m(n)不大於問題大小n的多項式倍數。任何抽象機器都擁有一複雜度類，此類包括可於此機器以多項式時間求解的問題。 以數學描述的話，則可說m(n).

BPP (複雜度)和多項式時間 · P (複雜度)和多項式時間 · 查看更多 »

图灵机

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

BPP (複雜度)和图灵机 · P (複雜度)和图灵机 · 查看更多 »

素数

質--數（Prime number），又称素--数，指在大於1的自然数中，除了1和該数自身外，無法被其他自然数整除的数（也可定義為只有1與該數本身两个正因数的数）。大於1的自然數若不是質數，則稱之為合數。例如，5是個質數，因為其正因數只有1與5。而6則是個合數，因為除了1與6外，2與3也是其正因數。算術基本定理確立了質數於數論裡的核心地位：任何大於1的整數均可被表示成一串唯一質數之乘積。為了確保該定理的唯一性，1被定義為不是質數，因為在因式分解中可以有任意多個1（如3、1×3、1×1×3等都是3的有效因數分解）。 古希臘數學家歐幾里得於公元前300年前後證明有無限多個質數存在（欧几里得定理）。現時人們已發現多種驗證質數的方法。其中試除法比較簡單，但需時較長：設被測試的自然數為n，使用此方法者需逐一測試2與\sqrt之間的整數，確保它們無一能整除n。對於較大或一些具特別形式（如梅森數）的自然數，人們通常使用較有效率的演算法測試其是否為質數（例如277232917-1是直至2017年底為止已知最大的梅森質數）。雖然人們仍未發現可以完全區別質數與合數的公式，但已建構了質數的分佈模式（亦即質數在大數時的統計模式）。19世紀晚期得到證明的質數定理指出：一個任意自然數n為質數的機率反比於其數位（或n的對數）。 許多有關質數的問題依然未解，如哥德巴赫猜想（每個大於2的偶數可表示成兩個素數之和）及孿生質數猜想（存在無窮多對相差2的質數）。這些問題促進了數論各個分支的發展，主要在於數字的解析或代數方面。質數被用於資訊科技裡的幾個程序中，如公鑰加密利用了難以將大數分解成其質因數之類的性質。質數亦在其他數學領域裡形成了各種廣義化的質數概念，主要出現在代數裡，如質元素及質理想。.

BPP (複雜度)和素数 · P (複雜度)和素数 · 查看更多 »

EXPTIME

在計算複雜性理論裡面，EXPTIME（有時稱作EXP）這個複雜度類是一些決定型問題的集合，這些問題可以使用圖靈機在O(2p(n))的時間內解決，這裡的p(n)代表的是n的某個多項式。 用DTIME來定義，則是 我們已經知道 另外，根據時間譜系理論（time hierarchy theorem）以及空間譜系理論（space hierarchy theorem）， 所以至少第一條包含關係中，前三個包含關係中的一個，以及後三個包含關係中的一個，必然是完整包含（沒有相等可能），但是我們還不知道那一個是。多數人相信這一些複雜度類全部都不相等。另外我們已知如果，則，這裡的NEXPTIME是在指數時間內可以使用非確定型圖靈機解決的問題。更精確的說，EXPTIME ≠ NEXPTIME若且唯若存在一個稀疏語言，在NP裡面且不在P內。 EXPTIME也可以用空間的方式來定義，等同於APSPACE這個複雜度類。APSPACE的意思是包含了所有可以用交替式圖靈機在多項式空間內解決的問題。這種定義方式也是一種看出PSPACE \subseteq EXPTIME的方式，因為已知交替式圖靈機至少跟確定型圖靈機計算能力一樣。 EXPTIME是指數譜系（exponential hierarchy）內的其中一個複雜度類。2-EXPTIME這個複雜度類則使用類似EXPTIME的定義方式，但是使用雙指數函數（Double exponential function）的時間限制2^。使用類似方式可以類推出更高的時間上限。.

BPP (複雜度)和EXPTIME · EXPTIME和P (複雜度) · 查看更多 »

NP (複雜度)

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

BPP (複雜度)和NP (複雜度) · NP (複雜度)和P (複雜度) · 查看更多 »

RP (複雜度)

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

BPP (複雜度)和RP (複雜度) · P (複雜度)和RP (複雜度) · 查看更多 »