BPP (複雜度)
在計算複雜度理論裡面，BPP是在多項式時間內以機率圖靈機解出的問題的集合, 並且對所有的輸入，輸出結果有錯誤的概率在1/3之內。BPP這個簡寫代表"Bounded-error"(有限錯誤)，"Probabilistic"(機率的)，"Polynomial time"(多項式時間)。 要是一個問題在BPP集合裡面，則存在一個演算法，此演算法允許轉硬幣作隨機的決定，並在多項式時間內結束。 對這個演算法的任何輸入，他都要在小於1/3的錯誤概率…
标签：#機率複雜度類
共 9 篇文章
BQP (複雜度)
在計算複雜度理論內，有限錯誤量子多項式時間（，）是一個決定性問題的複雜度類，並且其內的問題可以在多項式時間內以量子電腦解決，錯誤的機率小於1/3。BQP也可以視為是複雜度類BPP的量子電腦版。 換句話說，對BQP裡面的問題，存在一個使用量子電腦的演算法（量子演算法）花費多項式時間運作，並且有很高的機率回答正確的答案。對任何狀況，回答錯誤答案的機率小於三分之一。 與其他「有限錯誤」的機率演算法相同，這裡所提到的1/3是一個比較隨意的定義。…
交互式证明系统
在计算复杂性理论中，交互式证明体系（以下简称交互证明）是一类计算模型。像其它计算模型一样，交互证明的目标是：对一个语言L，和一个给定的输入x，判断x是否在L中。交互证明由两个实体：验证者（verifier）和证明者（prover）组成，两者都可以看作是某类图灵机。而它的计算过程为：给定了输入x，通过验证者和证明者之间交换信息，最终，由验证者来根据证明者给出的信息，判断给定的输入是不是在语言L中。 交互证明的基本假设是：证明者在计算能力上…
PP (複雜度)
在計算複雜度理論內，PP是一個複雜度類，包含可以在多項式時間裡面以概率圖靈機解決，無論輸入如何錯誤率均小於1/2的決定型問題。PP這個縮寫即代表了概率多項式時間（probabilistic polynomial time）。這個複雜度類是由Gill於1977年定義。 相關條目 PostBQP 參考資料 參考書目 . . . 外部連結 *[https://complexityzoo.uwaterloo.ca/Complexity_Zoo:…
L (複雜度)
L也稱為LSPACE或DLOGSPACE，是计算复杂度理论中能被确定型图灵机利用對數空间解决的判定问题集合。 对数空间是指与输入规模成对数大小关系的可写的储存空间，大多数对数空间（LOGSPACE）算法以这种方式储存。 相关复杂度类 FL 和功能性問題相關的類別是FL，在计算复杂度理论，FL是一个复杂度类，是能被确定型图灵机在对数空间下解决的函数问题的集合。 依照同样的原理，可以定义相应的FP，FNP，TFNP。对数空间规约在定义NL-…
RP (複雜度)
在複雜度理論內，RP（"隨機多項式時間"）是一個有關機率圖靈機的複雜度類，並且存在以下特性： 此演算法的运行时间不超过一个以输入长度为自变量的多项式函数 如果輸入的答案為非，此演算法會回傳NO 如果輸入的答案為是，則回傳YES的機率至少1/2（其餘的機率則是回傳NO）。 換句話說，這個演算法允許在操作的時候進行全然機率的猜測。這個演算法會回傳YES的狀況必然是輸入為真的狀況；因此如果這個演算法說了YES，那我們就知道了這個輸入必定為是：…
ZPP (複雜度)
在計算複雜度理論內, ZPP（zero-error probabilistic polynomial time，零錯誤概率多項式時間）是一個與機率圖靈機有關的的複雜度類，並且存在以下特點： 這機器永遠會給出正確的"是"或者"否"的答案。 這個機器平均運作的時間是多項式時間以內。 換句話說，有一個演算法會在運作時使用一個完美隨機的硬幣，並且永遠回傳正確的答案（這種演算法被稱作拉斯維加斯演算法（Las Vegas algorithm））。對…
低 (複雜度)
在計算複雜度理論內，若有A與B兩個複雜度類，且AB = A；或者說, A 在B成為他的神諭之後的複雜度等同於A，則我們說複雜度類別B比A要來的"低"。這陳述代表著一個可以解決問題類別A的機器，在獲得了在單位時間內解決問題類別B的能力之後，並沒有增加多餘的計算能力。特別是，這代表著如果B類別低於A類別，則B必然包含在A裡面。 較不正式的說，較低的關係不僅僅代表包含於B的問題可以被能夠解決A問題的機器所解決, 而且是"可以被簡單解決的"。一…
BPL (複雜度)
在計算複雜度理論領域內，BPL（有限錯誤機率對數空間，Bounded-error Probabilistic Logarithmic-space）或者叫做BPLP（有限錯誤機率對數空間多項式時間，Bounded-error Probabilistic Logarithmic-space Polynomial-time）是一個使用機率圖靈機可以在多項式時間時間以及對數空間解決的問題，但是有雙邊錯誤（two-sided error）。這個類…