ZPP (複雜度) 在計算複雜度理論內 ZPPzeroerror probabilistic polynomial time零錯誤概率多項式時間是一個與機率圖靈機有關的的複雜度類並且存在以下特點 這機器永遠會給出正確的是或者否的答案 這個機器平均運作的時間是多項式時間以內 換句話說有一個演算法會在運作時使用一個完美隨機的硬幣並且永遠回傳正確的答案這種演算法被稱作拉斯維加斯演算法Las Vegas algorithm對一個輸入大小為n的問題存在一個多項式pn令平均的運作時間小於pn有可能偶爾會超過 另外ZPP可以定義為一個問題的集合裡面每個問題都存在一個可以解決此問題的機率圖靈機且此機器性質如下 運轉時間永遠是多項式時間 會回傳YESNO或者DO NOT KNOW的答案 答案如果不是DO NOT KNOW就會是正確的答案 如果問題的正確答案是YES這機器回傳YES的機率至少是其他時候回傳DO NOT KNOW 如果問題的正確答案是NO這機器回傳NO的機率至少是其他時候回傳DO NOT KNOW 以上這兩個定義是相等的 ZPP的定義是基於概率圖靈機其他基於概率圖靈機的複雜度類包含了BPP和RP至於BQP 複雜度這個複雜度類則換成使用了量子電腦這種也是具有隨機性的電腦