posted on 1983-01-01, 00:00authored byRyan O'Donnell
In this paper we investigate the following question: if NP is slightly hard on average, is it very hard on average?
The computational result we prove essentially matches an information-theoretic bound