3 ms·
it's actually a very open question, even theoretically, whether we can build an "hard on average problem" from a "worst case hard problem" in NP. This is why we
by Vervious 4y ago
it's actually a very open question, even theoretically, whether we can build an "hard on average problem" from a "worst case hard problem" in NP. This is why we haven't yet managed to design cryptography from 3SAT, for instance.
- chrisandchips 4y agoThat's super interesting! I'd love get the names of some people working on that stuff.