識別不能

識別不能（しきべつふのう）とは、二つの確率変数を見分けることができないことを意味する。ただ、これらを「見分けようとする人」がどのようにして見分けるのか、どれだけの能力を持っているかによって、見分けられるか・見分けられないかは異なる。そのため、想定する「見分けるために使う能力」により、三つの定義がある。
情報論的識別不能.
formula_1を確率変数の族とする。
あるformula_2があって任意のformula_3に対しformula_4の従う確率分布とformula_5の従う確率分布が同一である時、族formula_6とformula_7は情報論的識別不能であるという。
二つの確率変数（の確率分布）が同一であれば、どんなに計算能力があろうとも見分けることができない。つまり、情報論的識別不能は、「どんなに計算能力があろうとも」見分けることができないことを意味する。
例：
formula_8とformula_11は異なる実験によって得られる確率変数であるが、共に、任意のformula_9ビット列が確率formula_17で生じる。よって、formula_18とformula_19は情報論的識別不能である。
統計的識別不能.
formula_20、formula_21を確率変数とする。
formula_20とformula_21との統計的距離をformula_24　により定義する。
formula_4とformula_5との統計的距離が、formula_9に対して無視できるとき、
すなわち任意の多項式formula_28に対し、あるformula_2があって任意のformula_30に対し、formula_31となる時、族formula_32とformula_33は統計的識別不能であるという。
二つの確率変数を見分けたい人が、いずれかの確率変数（の確率分布）によって選ばれた値を次々に観測し続けて、見分けることを考えよう。二つの確率分布が大きく異なる場合、観測値の頻度分布を求めることで、どちらの確率分布であるのかを見分けることができるだろう。逆に、確率分布がほとんど同じ場合、多くの値を観測したとしても見分けはつきにくい。統計的識別不可能は、多項式個の値を観測しても見分けがつかないことを意味する。
例：
formula_37では、0がformula_9個並んだものは生じず（formula_42）、それ以外のformula_9ビット列が確率formula_44で生じる。よって、formula_4とformula_5の統計的距離はformula_47である。
よって、formula_18とformula_49は統計的識別不能である。
計算量的識別不能.
任意の多項式時間機械formula_50 （識別機(distinguisher)という）と任意の多項式formula_28に対し、あるformula_2があって任意のformula_30に対し
formula_54となる時、formula_32とformula_33は計算量的識別不能であるという。
定義からわかるように、計算量的識別不能は、計算能力を多項式時間に限定した場合に、見分けることができないことを意味する。
例：
暗号理論の分野では、多くの計算量的識別不能を仮定している。例として以下のものがある．