No better ways to generate hard NP instances than picking uniformly at random

Distributed NP (DNP) problems are ones supplied with probability distributions of instances. It is shown that every DNP problem complete for P-time computable distributions is also complete for all distributions that can be sampled. This result makes the concept of average-case NP completeness robust and the question of the average-case complexity of complete DNP problems a natural alternative to P=?NP. Similar techniques yield a connection between cryptography and learning theory.