No better ways to generate hard NP instances than picking uniformly at random
R Impagliazzo, L LA - Proceedings [1990] 31st Annual …, 1990 - ieeexplore.ieee.org
R Impagliazzo, L LA
Proceedings [1990] 31st Annual Symposium on Foundations of …, 1990•ieeexplore.ieee.orgDistributed 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.
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.
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.
ieeexplore.ieee.org