Re:NP-Complete isn't (always) Hard
by Vervious on Tuesday February 21, 2023 @04:05PM
(#34887315)
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.
[ Parent
| on HN ]
Re:NP-Complete isn't (always) Hard
by chrisandchips on Tuesday February 21, 2023 @04:27PM
(#34887644)
That's super interesting! I'd love get the names of some people working on that stuff.