ZPP (複雜度)和機率圖靈機

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

ZPP (複雜度)和機率圖靈機之间的区别

ZPP (複雜度) vs. 機率圖靈機

在計算複雜度理論內, ZPP（zero-error probabilistic polynomial time，零錯誤概率多項式時間）是一個與機率圖靈機有關的的複雜度類，並且存在以下特點：. 在計算複雜性理論內，機率圖靈機是一個非決定型圖靈機，在每個轉折點根據某種概率分佈隨機選擇某種可行的轉變(transition)。 在轉變是均勻分佈機率的例子裡面，我們可以定義為決定型圖靈機多了一個新增的"寫入"指令，這一個寫入指令的值是所有圖靈機能用符號的均勻分佈機率選擇出的符號 (概括地說，這個寫入指令以相同的機率在紙帶上面寫入'1'或者'0'。) 另一個常用的定義是多了一條隨機紙帶，上面佈滿了許多隨機位元值的確定型圖靈機。 所以，機率圖靈機可以有隨機的結果(與決定型圖靈機不同)；給定一個輸入和一個狀態機，機器運作的時間長度會不同，或者甚至不會停止； 甚至，這機器可能在這一次操作下回傳為接受，下一次相同的輸入值卻回傳為拒絕。 因此如何去理解被一個機率圖靈機接受字串的方式可以用許多不同的方式定義。 同時也有許多種因為我們對accept方式的不同，而產生了許多的多項式時間隨機複雜度類，包含了 RP，Co-RP，BPP and ZPP。 如果我們把多項式時間的限制改成對數空間的限制，我們則有了跟上面雷同的RL，Co-RL，BPL，和ZPL。如果我們同時限制兩者，則有了RLP，Co-RLP，BPLP，和ZPLP。 隨機計算對於定義大多數的交互式證明系統也是極為重要的，因為驗證者機器需要隨機性來避免被全能的證明者預測或者欺騙。 例如說，IP這個類別等同 PSPACE，但是如果把驗證者的隨機性移除，我們就只有NP，一個一般而言相信(但尚未證明)是比起IP要小的複雜度類。 複雜度理論的其中一個重點問題是：是否隨機性增加了演算法的能力？ 換句話說，是否有問題在多項式時間內可以以概率圖靈機解決但是不能以決定型圖靈機解決？或者是決定型圖靈機可以在至多只有多項式時間的變慢之下，完全的模仿隨機圖靈機的動作？現今的研究者大部分相信後者，這同時可以推出 P.

复杂性类

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

ZPP (複雜度)和复杂性类 · 复杂性类和機率圖靈機 · 查看更多 »

量子计算机

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

ZPP (複雜度)和量子计算机 · 機率圖靈機和量子计算机 · 查看更多 »

RP (複雜度)

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

RP (複雜度)和ZPP (複雜度) · RP (複雜度)和機率圖靈機 · 查看更多 »