Francais | English | Espanõl

From Wikipedia, the free encyclopedia

In algorithmic information theory, if {D_n}_{n ∈ N} and {E_n}_{n ∈ N} are distribution ensembles (on Ω) then we say they are computationally indistinguishable if for any probabilistic, polynomial time algorithm A and any polynomal function p(.) there is some m such that for all n > m:

<math>\vert\operatorname{Prob}_A(D_n)-\operatorname{Prob}_A(E_n)\vert<\frac{1}{p(n)}</math>

where Prob_A(D_n) is the probability that A accepts x where x is chosen according to the distribution D_n.

This article incorporates material from computationally indistinguishable on PlanetMath, which is licensed under the GFDL.