upvote
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.

reply
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.

reply
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

reply
Yeah no. No proper CS course claims that NP is defined to be “hard” problems (whatever you plugin for “hard”). NP is defined in a way where computation models EXIST (be it non deterministic Turing machine or witnesses).

The connection to solution space is also iffy and usually not how people introduce or primarily think of NP.

All your claimed definitons imply that NP and P are disjoint which clearly isn’t the case. I would be more careful

reply