比浏览器更快的访问！
22 关系: AKS質數測試，多項式時間，子集，常数，低 (複雜度)，啟示圖靈機，图灵机，BQP (複雜度)，素数，猜想，随机化算法，EXPTIME，问题，量子计算机，NP (複雜度)，NP完全，P (複雜度)，PH (複雜度)，PP (複雜度)，RP (複雜度)，ZPP (複雜度)，概率。
AKS質數測試
AKS質數測試（又被稱為 Agrawal–Kayal–Saxena質數測試 和 Cyclotomic AKS test）是一個決定型質數測試演算法 ，由三個來自的計算機科學家，、和，在2002年8月6日發表於一篇題為質數屬於P的論文。Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "", Annals of Mathematics 160 (2004), no.
新！!: BPP (複雜度)和AKS質數測試 · 查看更多 »
多項式時間
多項式時間（Polynomial time）在計算複雜度理論中，指的是一個問題的計算時間m(n)不大於問題大小n的多項式倍數。任何抽象機器都擁有一複雜度類，此類包括可於此機器以多項式時間求解的問題。 以數學描述的話，則可說m(n).
新！!: BPP (複雜度)和多項式時間 · 查看更多 »
子集
子集，為某個集合中一部分的集合，故亦稱部分集合。 若A和B为集合，且A的所有元素都是B的元素，则有：.
新！!: BPP (複雜度)和子集 · 查看更多 »
常数
常数又稱定數，是指一个数值固定不变的常量，例如圆周率\pi\,、自然对数的底e，与之相反的是變數。 在物理學上，很多經測量得出的數值都被稱為常數。例如萬有引力常數和地表重力加速度等。但有研究表明，部分這類常数并不是恒定不变的，因此就被稱作“不定常数”（inconstant constant）和“不恒定的常数”（not-so-constant constant）。.
新！!: BPP (複雜度)和常数 · 查看更多 »
低 (複雜度)
在計算複雜度理論內，若有A與B兩個複雜度類，且AB.
新！!: BPP (複雜度)和低 (複雜度) · 查看更多 »
啟示圖靈機
#重定向 預言機.
新！!: BPP (複雜度)和啟示圖靈機 · 查看更多 »
图灵机
图灵机（），又称确定型图灵机，是英国数学家艾倫·图灵于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。.
新！!: BPP (複雜度)和图灵机 · 查看更多 »
BQP (複雜度)
在計算複雜度理論內，有限錯誤量子多項式時間（bounded error quantum polynomial time，BQP）是一個決定性問題的複雜度類，並且其內的問題可以在多項式時間內以量子電腦解決，錯誤的機率小於1/3。BQP也可以視為是複雜度類BPP的量子電腦版。 換句話說，對BQP裡面的問題，存在一個使用量子電腦的演算法（量子演算法）花費多項式時間運作，並且有很高的機率回答正確的答案。對任何狀況，回答錯誤答案的機率小於三分之一。 與其他「有限錯誤」的機率演算法相同，這裡所提到的1/3是一個比較隨意的定義。如果原本演算法的錯誤機率比較大，我們可以運作多次該演算法，然後取多數回答正確的答案以取得比較高的準確率。詳細的分析顯示錯誤的下限可以高達1/2 − n−c或者低達2−nc，所包含的題目範圍均不會有變化。這裡c是一個正數的常數，n是輸入的長度。.
新！!: BPP (複雜度)和BQP (複雜度) · 查看更多 »
素数
質--數（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 (複雜度)和素数 · 查看更多 »
猜想
數學中的猜想是在根據不完全資訊下的結論及命题，是不知其真假的數學敘述，它可能為真，暫時未被證明或反證 。某些猜想會稱為「假設」，尤其是當它是針對某些問題提出的答案。 像黎曼猜想（目前仍然是猜想）或是費馬最後定理（以往是猜想，一直到1995年才得證）都對數學歷史帶來許多的進展，而且為了證明這些猜想，也發展了新的數學領域。 當猜想被證明後，它便會成為定理。猜想只要未成為定理，數學家都要小心在邏輯結構之中使用這些猜想。猜想主要因為類比推理和偶然發現的巧合而出現。數學家通常會使用不完全歸納法，來測試自己的猜想。例如費馬曾經根據首四個費馬數是素數，便猜想所有費馬數都是素數（此猜想已被推翻）。.
新！!: BPP (複雜度)和猜想 · 查看更多 »
随机化算法
随机化算法（randomized algorithm），是这样一种算法，在算法中使用了随机函数，且随机函数的返回值直接或者间接的影响了算法的执行流程或执行结果。就是将算法的某一步或某几步置于运气的控制之下，即该算法在运行的过程中的某一步或某几步涉及一个随机决策，或者说其中的一个决策依赖于某种随机事件。 Category:算法分析.
新！!: BPP (複雜度)和随机化算法 · 查看更多 »
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 · 查看更多 »
问题
问题很难有一个确定的、无异议的定义，但是，一般来说都问题包含有以下三个基本成分：.
新！!: BPP (複雜度)和问题 · 查看更多 »
量子计算机
量子计算机（quantum computer）是一种使用量子邏輯進行通用計算的設備。不同於电子计算机（或稱傳統電腦），量子計算用來存儲數據的對象是量子比特，它使用量子演算法來進行數據操作。马约拉纳费米子反粒子就是自己本身的属性，或许是令量子计算机的制造变成现实的一个关键。.
新！!: BPP (複雜度)和量子计算机 · 查看更多 »
NP (複雜度)
非定常多项式（non-deterministic polynomial，缩写：NP）时间复杂性类，或称非确定性多项式时间复杂性类，包含了可以在多项式时间内，对一个判定性算法问题的实例，一个给定的解是否正确的算法问题。 NP是计算复杂性理论中最重要的复杂性类之一。它包含复杂性类P，即在多项式时间内可以验证一个算法问题的实例是否有解的算法问题的集合；同时，它也包含NP完全问题，即在NP中“最难”的问题。计算复杂性理论的中心问题，P/NP问题即是判断对任意的NP完全问题，是否有有效的算法，或者NP与P是否相等。.
新！!: BPP (複雜度)和NP (複雜度) · 查看更多 »
NP完全
NP完全或NP完備（NP-Complete，縮寫為NP-C或NPC），是計算複雜度理論中，決定性問題的等級之一。NPC問題，是NP（非決定性多項式時間）中最難的決定性問題。因此NP完備問題應該是最不可能被化簡為P（多項式時間可決定）的決定性問題的集合。若任何NPC問題得到多項式時間的解法，那此解法就可應用在所有NP問題上。更詳細的定義容下敘述。 一個NPC問題的例子是子集合加總問題，題目為 這個問題的答案非常容易驗證，但目前沒有任何一個夠快的方法可以在合理的時間內（意即多項式時間）找到答案。只能一個個將它的子集取出來一一測試，它的時間複雜度是Ο(2n)，n是此集合的元素數量。.
新！!: BPP (複雜度)和NP完全 · 查看更多 »
P (複雜度)
在計算複雜度理論中，P 是在複雜度類問題中可於決定性圖靈機以多項式量級（或稱多項式時間）求解的決定性問題。 P通常表示那類可以"有效率地解決"或"溫馴"的可計算型問題，就算指數級非常高也可以算作"溫馴"，例如RP與BPP問題。當然P類存在很多現實處理上一點也不溫馴的問題，例如一些至少需要n1000000指令來解決的問題。很多情況下存在著更難的複雜度問.
新！!: BPP (複雜度)和P (複雜度) · 查看更多 »
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).
新！!: BPP (複雜度)和PH (複雜度) · 查看更多 »
PP (複雜度)
在計算複雜度理論內，PP是一個複雜度類，包含可以在多項式時間裡面以概率圖靈機解決，無論輸入如何錯誤率均小於1/2的決定型問題。PP這個縮寫即代表了概率多項式時間(probabilistic polynomial time)。這個複雜度類是由Gill於1977年定義。 Lance Fortnow.
新！!: BPP (複雜度)和PP (複雜度) · 查看更多 »
RP (複雜度)
在複雜度理論內，RP（"隨機多項式時間"）是一個有關機率圖靈機的複雜度類，並且存在以下特性：.
新！!: BPP (複雜度)和RP (複雜度) · 查看更多 »
ZPP (複雜度)
在計算複雜度理論內, ZPP（zero-error probabilistic polynomial time，零錯誤概率多項式時間）是一個與機率圖靈機有關的的複雜度類，並且存在以下特點：.
新！!: BPP (複雜度)和ZPP (複雜度) · 查看更多 »
概率
--率，舊稱--率，又称或然率、機會率或--、可能性，是数学概率论的基本概念，是一个在0到1之间的实数，是对随机事件发生之可能性的度量。 概率常用來量化對於某些不確定命題的想法"Kendall's Advanced Theory of Statistics, Volume 1: Distribution Theory", Alan Stuart and Keith Ord, 6th Ed, (2009), ISBN 978-0-534-24312-8，命題一般會是以下的形式：「某個特定事件會發生嗎？」，對應的想法則是：「我們可以多確定這個事件會發生？」。確定的程度可以用0到1之間的數值來表示，這個數值就是機率William Feller, "An Introduction to Probability Theory and Its Applications", (Vol 1), 3rd Ed, (1968),Wiley,ISBN 978-0-471-25708-0。因此若事件發生的機率越高，表示我們越認為這個事件可能發生。像丟銅板就是一個簡單的例子，正面朝上及背面朝上的兩種結果看來機率相同，每個的機率都是1/2，也就是正面朝上及背面朝上的機率各有50%。 這些概念可以形成機率論中的數學公理（參考概率公理），在像數學、統計學、金融、博弈論、科學（特別是物理）、人工智慧/機器學習、電腦科學及哲學等學科中都會用到。機率論也可以描述複雜系統中的內在機制及規律性。.
新！!: BPP (複雜度)和概率 · 查看更多 »
