開放式問題

在計算複雜度理論里，有一個「BPP」的概念，它描述了一種問題的集合，即「Bounded-error」，「Probabilistic」，「Polynomial time」，指在多項式時間內以概率圖靈機（非決定性圖靈機）解出的問題的集合, 並且對所有的輸入，輸出結果有錯誤的概率為0到1/2的範圍內的一個任意值（但不包含0與1/2）。

舉例來說，如果一個問題屬於BPP所描述的問題集合，則必然存在一個算法，此算法允許轉硬幣作隨機的決定，並在多項式時間內結束。 對這個算法的任何輸入，他都要在(0,1/2)的錯誤概率內給出正確判斷，不論這一個問題的答案是「正確」或者「錯誤」）。

另一個概念「$P$」，是指在複雜度類問題中決定性圖靈機在多項式時間內求解的決定性問題的集合。

一個問題如果屬於「$P$」，並且假設存在某種條件達成$BPP=P$時，我們說這個問題是一個開放式問題。