識別不能

識別不能（しきべつふのう）とは、二つの確率変数を見分けることができないことを意味する。ただ、これらを「見分けようとする人」がどのようにして見分けるのか、どれだけの能力を持っているかによって、見分けられるか・見分けられないかは異なる。そのため、想定する「見分けるために使う能力」により、三つの定義がある。

情報論的識別不能
を確率変数の族とする。

あるがあって任意のに対しの従う確率分布との従う確率分布が同一である時、族とは情報論的識別不能であるという。

二つの確率変数（の確率分布）が同一であれば、どんなに計算能力があろうとも見分けることができない。つまり、情報論的識別不能は、「どんなに計算能力があろうとも」見分けることができないことを意味する。

例：
 確率変数 ：公正なコインを回ふる、という実験の結果。コインの表が出たら1、裏が出たら0、として、個の0,1列で表現する。
 確率変数 ：公正な2つのコインを回ふって、各回に同じ面が出るか、という実験の結果。2つのコインで同じ面が出たら1、異なる面が出たら0、として個の0,1列で表現する。

とは異なる実験によって得られる確率変数であるが、共に、任意のビット列が確率で生じる。よって、とは情報論的識別不能である。

統計的識別不能
、を確率変数とする。
ととの統計的距離を　により定義する。
ととの統計的距離が、に対して無視できるとき、
すなわち任意の多項式に対し、あるがあって任意のに対し、となる時、族とは統計的識別不能であるという。

二つの確率変数を見分けたい人が、いずれかの確率変数（の確率分布）によって選ばれた値を次々に観測し続けて、見分けることを考えよう。二つの確率分布が大きく異なる場合、観測値の頻度分布を求めることで、どちらの確率分布であるのかを見分けることができるだろう。逆に、確率分布がほとんど同じ場合、多くの値を観測したとしても見分けはつきにくい。統計的識別不可能は、多項式個の値を観測しても見分けがつかないことを意味する。

例：
 確率変数 ：公正なコインを回ふる、という実験の結果。コインの表が出たら1、裏が出たら0、として、個の0,1列で表現する。
 確率変数 ：と同じ実験をするが、回続けて裏が出たら、最初からやり直すという実験の結果。

では、0が個並んだものは生じず（）、それ以外のビット列が確率で生じる。よって、との統計的距離はである。
よって、とは統計的識別不能である。

計算量的識別不能

任意の多項式時間機械 （識別機(distinguisher)という）と任意の多項式に対し、あるがあって任意のに対し
となる時、とは計算量的識別不能であるという。

定義からわかるように、計算量的識別不能は、計算能力を多項式時間に限定した場合に、見分けることができないことを意味する。

例：
暗号理論の分野では、多くの計算量的識別不能を仮定している。例として以下のものがある．
 平方剰余と平方非剰余
 ディフィー・ヘルマン鍵共有の鍵と乱数

関連項目
 暗号理論

しきへつふのう