識別不能
出典: フリー百科事典『ウィキペディア（Wikipedia）』
（計算量的識別不能から転送）
識別不能（しきべつふのう）
情報論的識別不能
あるk0があって任意のk>k0に対しXkの従う確率分布とYkの従う確率分布が同一である時、族{Xk}k∈Nと{Yk}k∈Nは情報論的識別不能であるという。
統計的識別不能
A、Bを確率変数とする。 AとBとの統計的距離を∑xはkビットのビット列|Pr(A=x)-Pr(B=x)| により定義する。 XkとYkとの統計的距離がkに対して無視できるとき、 すなわち任意の多項式Pに対し、あるk0があって任意のk>k0に対し、∑xはkビットのビット列|Pr(Xk=x)-Pr(Yk=x)|<1/P(k)となる時、族{Xk}k∈Nと{Yk}k∈Nは統計的識別不能であるという。
計算量的識別不能
任意の多項式時間機械D （識別機(distinguisher)という）と任意の多項式Pに対し、あるk0があって任意のk>k0に対し |Pr(D(Xk)=1)-Pr(D(Yk)=1)|<1/P(k)となる時、XkとYkは計算量的識別不能であるという。
