No better ways to generate hard NP instances than picking uniformly at random
- 1 January 1990
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 812-821 vol.2
- https://doi.org/10.1109/fscs.1990.89604
Abstract
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.Keywords
This publication has 14 references indexed in Scilit:
- Matrix decomposition problem is complete for the average casePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A hard-core predicate for all one-way functionsPublished by Association for Computing Machinery (ACM) ,1989
- A theory of learning simple concepts under simple distributions and average case complexity for the universal distributionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- Random instances of a graph coloring problem are hardPublished by Association for Computing Machinery (ACM) ,1988
- On the existence of pseudorandom generatorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Reductions among prediction problems: on the difficulty of predicting automataPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Average Case Complete ProblemsSIAM Journal on Computing, 1986
- A theory of the learnableCommunications of the ACM, 1984
- Universal classes of hash functionsJournal of Computer and System Sciences, 1979
- A formal theory of inductive inference. Part IInformation and Control, 1964