Comment by ggm
10 hours ago
I'd be very surprised if the number of meaningfully hard problems is capable of being bounded. As a proposition it feels opposite to almost everything else we believe about numbers. But, that's just my naieve view.
10 hours ago
I'd be very surprised if the number of meaningfully hard problems is capable of being bounded. As a proposition it feels opposite to almost everything else we believe about numbers. But, that's just my naieve view.
I think there's a weak claim that I'm happy to make and then a much stronger one. The set of hard problems in general is vastly larger than hard problems that are considered useful to cryptographers. The latter is very much finite, and hardness in cryptography is rarely a formal affair either. At best cryptographers can prove reductions to problems that they think are hard, but they can't prove the hardness of the problems themselves. We don't know that the ECDLP is hard, for example. And I'd be very surprised if complexity theorists were able to say anything about these kind of hard problem in my lifetime.
For the stronger claim, if you pick a complexity class like NP and assume P!=NP, I'm pretty confident you could find as many problems as you want in NP that aren't in P and that all look meaningfully different from each other. So the claim that these are bounded is probably false. But hard problems in the sense of NP-hardness isn't sufficient to make them useful to cryptographers.