COMPUTATIONAL INDISTINGUISHABILITY - ALGORITHMS VS. CIRCUITS

We present a simple proof of the existence of a probability ensemble w ith tiny support which cannot be distinguished from the uniform ensemb le by any recursive computation. Since the support is tiny (i.e., sub- polynomial), this ensemble can be distinguished from the uniform ensem ble by a (non-uniform) family of small circuits. It also provides an e xample of an ensemble which cannot be (recursively) distinguished from the uniform by one sample, but can be so distinguished by two samples . In case wt: only wish to fool probabilistic polynomial-time algorith ms the ensemble can be constructed in super-exponential time.