Computationally indistinguishable

From Wikipedia, the free encyclopedia

You have new messages (last change).

In algorithmic information theory, if {Dn}n ∈ N and {En}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:

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

where ProbA(Dn) is the probability that A accepts x where x is chosen according to the distribution Dn.

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

Retrieved from "http://en.wikipedia.org../../../c/o/m/Computationally_indistinguishable.html"