logoalt Hacker News

xlii • today at 12:59 PM • 1 reply • view on HN

E.g. NP is a problem that's easy to check, but not easy to solve. NP is type of a problem like one for finding people: it's easy to confirm (is Mr. X in the room?), but there's no quick way to find solution (where is Mr. X).


Replies

TeMPOraL • today at 1:12 PM

This kind of explanation is arguably doing more harm than good, for at least several reasons:

- The property of a problem being "easy to check, but not easy to solve" is an extremely useful one[0]. It's also not inherent to NP problems. Most problems that have this property are not NP.

- The explanation omits entirely a different aspect, that's closer to a characteristic of NP problems: that they're all equivalent to each other mathematically, so if you find an efficient solution for one, you found it for all of them.

--

[0] - Especially so in the age of LLMs, as it's almost a definition of "what LLMs can beat humans at today"/what we can reliably use them for.

➕ show 1 reply