logoalt Hacker News

tux3today at 8:42 AM1 replyview on HN

You can make as many slight variations as you want by creating a specific instantiation of a hard problem with different constants. But we don't know how many meaningfully different hard problems exist.

These are problems that have been studied for many years, that are more-or-less central to mathematics, and where we have good reason to think that an efficient solution would be extremely surprising.

If you have much lower standards, there's going to be infinely many that I can't personally solve. Or if you have impractically high standards, there could be zero hard problems, if they just so happen to all have efficient solutions that we haven't found yet. We can't formally prove any of these are hard.


Replies

ggmtoday at 10:03 AM

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.

show 1 reply