text: 在演算法分析和密碼學中，如果沒有高效的演算法可以區分兩個分佈族之間的差異的。正式定義.令formula_1和formula_2 是兩個，下標"n"是。如果對於任意的機率多項式時間演算法 "A"，以下值是一個"n"上的可忽略函式，則我們說它們在計算上是不可區分的：formula_3記為formula_4。 換言之，在formula_5時，每個高效的演算法"A"的行為在"D""n"和"E""n"上不會有明顯變化。對計算不可區分性的另一種解釋是，主動嘗試區分這兩個集合的多項式時間演算法不能實現目標：任何這樣的演算法的表現與單純猜測相比，優勢可以忽略不計。相關概念.定義中隱含的條件是演算法formula_6必須根據其中一個分佈的單個樣本中決定。有人可能會設想這樣一種情況，即演算法為了區分兩個分佈，可以根據需要訪問儘可能多的樣本。因此，兩個分佈無法由多項式時間演算法透過觀察多個樣本區分的情形，被稱為無法透過多項式時間取樣區分。:107 如果多項式時間演算法可以在多項式時間內生成樣本，或者可以訪問為其生成樣本的隨機預言機，那麼多項式時間取樣的不可區分性等同於計算不可區分性。:108本條目含有來自PlanetMath《computationally indistinguishable》的內容，版權遵守協議。
metadata.dataset: erhwenkuo/wikipedia-zhtw
metadata.title: 計算不可區分性
metadata.url: https://zh.wikipedia.org/wiki?curid=8107130