logoalt Hacker News

TeMPOraL • today at 1:12 PM • 2 replies • view on HN

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.


Replies

less_less • today at 7:53 PM

No, neither of these.

Very roughly, P = "easy to solve", and NP = "easy to check whether a proposed solution is correct". All problems in P are also in NP. The P =? NP question is whether the reverse is also true. A problem is "NP-hard" if it's at least as hard (in some very particular sense) as every problem in NP, and it's "NP-complete" if it's NP-hard and also itself in NP. It's these NP-complete problems which are in some sense all equivalent to each other.

There are still a lot of technical details omitted here. To scratch the surface:

"Problem" aka "Language" = "yes-no questions about strings", so for example "is this string the base-10 representation of a square integer?" (in P, and therefore also in NP) or "does this string represent a square grid of numbers that's a Sudoku (generalized to allow larger grids than 9x9) with at least one solution?" (in NP, and in fact NP-complete). "Easy" = "there exists a deterministic Turing machine which correctly answers the question on every input, and always runs in a number of steps which is less than some particular polynomial in the length of the input string". (In the real world, though, "polynomial-time" is not the same thing as "easy".) A language L being NP-hard means that for any NP language M, there's a polynomial-time deterministic Turing machine which maps M-inputs to L-inputs, where yes-instances map to yes-instances and no to no. Swapping yes and no is not allowed. For NP problems you only have to be able to check solutions in poly-time if the solution indicates that the answer is "yes". The corresponding family where you can check "no" quickly is called co-NP, and it is believed that NP != co-NP. Etc etc etc.

xlii • today at 2:04 PM

And yet the same explanation is used as computer science courses in universities. Simplifications have their limits. In short P and NP boils to polynomial and non-polynomial solution space.

And yet you haven't pointed it out. I'd recommend reading this blog post that mentions the limits and consequences of simplifications: https://nedbatchelder.com/blog/201711/toxic_experts

➕ show 1 reply