識別不能
任意の多項式時間機械 D {\displaystyle D} (識別機(distinguisher)という)と任意の多項式 P {\displaystyle P} に対し、ある k 0 {\displaystyle k_{0}} があって任意の k > k 0 {\displaystyle k>k_{0}} に対し | P r ( D ( X k ) = 1 ) − P r ( D ( Y k ) = 1 ) | < 1 / P ( k ) {\displaystyle |Pr(D(X_{k})=1)-Pr(D(Y_{k})=1)|<1/P(k)} となる時、 { X k } k ∈ N {\displaystyle \{X_{k}\}_{k\in N}} と { Y k } k ∈ N {\displaystyle \{Y_{k}\}_{k\in N}} は計算量的識別不能であるという。
定義からわかるように、計算量的識別不能は、計算能力を多項式時間に限定した場合に、見分けることができないことを意味する。
例: 暗号理論の分野では、多くの計算量的識別不能を仮定している。例として以下のものがある.
平方剰余と平方非剰余
ディフィー・ヘルマン鍵共有の鍵と乱数