4 ms·
All problems in NP seem to be hard to solve and easy to verify. This is actually a really common property.
by Kenji 6y ago
All problems in NP seem to be hard to solve and easy to verify. This is actually a really common property.
- metiscus 6y agoThis comment was dead and I couldn't understand why it was flagged as it didn't seem to violate any rules. Moreover in my experience I tend to agree that most NP problems do seem to have this property. Can someone who downvoted/flagged or is otherwise knowledgeable about the subject chime in and correct/ teach me something new?
- grzm 6y agoIt wasn't flagged. It looks like Kenji is banned. Their comments are [dead], not [flagged][dead].
- metiscus 6y agoThat's an interesting point. I looked at the comment history after you mentioned it, and saw that too. Thanks for replying!
- solveit 6y agoFwiw, NP includes P, so it's not true that problems in NP are hard to solve, easy to verify. You want to limit the statement to NP-complete problems. Even then, it's only true that solving the problems in full generality is (conjectured) hard. Individual instances can be easy, and in some applications, it may be the case that all/most problems that occur in practice are easy. Even SAT can be easy in practice, and modern SAT solvers solve instances with millions of variables every day.
- deleted 6y ago[deleted]
- bawolff 6y agoWhile all problems that are NP-hard (to be pedantic different from just NP) have that property, for crypto you want things to be uniformly hard (i.e. a randomly generated instance is hard). That's a much rarer property.