識別不能

識別不能（しきべつふのう）

情報論的識別不能

{X_k}_k∈N、{Y_k}_k∈Nを確率変数の族とする。

あるk₀があって任意のk>k₀に対しX_kの従う確率分布とY_kの従う確率分布が同一である時、族{X_k}_k∈Nと{Y_k}_k∈Nは情報論的識別不能であるという。

統計的識別不能

A、Bを確率変数とする。 AとBとの統計的距離を∑_{xはkビットのビット列}|Pr(A=x)-Pr(B=x)|　により定義する。 X_kとY_kとの統計的距離がkに対して無視できるとき、 すなわち任意の多項式Pに対し、あるk₀があって任意のk>k₀に対し、∑_{xはkビットのビット列}|Pr(X_k=x)-Pr(Y_k=x)|<1/P(k)となる時、族{X_k}_k∈Nと{Y_k}_k∈Nは統計的識別不能であるという。

計算量的識別不能

任意の多項式時間機械D （識別機(distinguisher)という）と任意の多項式Pに対し、あるk₀があって任意のk>k₀に対し |Pr(D(X_k)=1)-Pr(D(Y_k)=1)|<1/P(k)となる時、X_kとY_kは計算量的識別不能であるという。

関連項目

• 暗号理論