This is really annoying because it's so easy to do better: instead of saying (like the article does) "NP is a class of problems that are hard to solve yet easy to verify", you just have to say "NP is a class of problems that are easy to verify, no matter how hard they are to solve".

With this small change it's much easier to see that P is inside NP, whereas with the original explanation, most people have to re-calibrate their understanding of what NP is when they learn that it actually does include P.

It also makes it easy to see that "P vs NP" is just the question: "are there really any hard problems that are easy to verify, or is every problem like that easy and we just aren't very good at solving some of them?"

https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/AW09/AW0...

https://www.scottaaronson.com/papers/pnp.pdf

> "Although there’s no “purely mechanical procedure” to determine if a mathematical statement S is true or false, there is a mechanical procedure to determine if S has a proof of some bounded length n: simply enumerate over all proofs of length at most n, and check if any of them prove S. This method, however, takes exponential time. The P ? = NP problem asks whether there’s a fast algorithm to find such a proof (or to report that no proof of length at most n exists), for a suitable meaning of the word “fast.”"

"Fast" seems to mean polynomial time (which can still be a very long time, but not blowing up in the way that exponential time does). The paper gives some clear examples:

> "Think of a large jigsaw puzzle with (say) 10^1000 possible ways of arranging the pieces, or an encrypted message with a similarly huge number of possible decrypts, or an airline with astronomically many ways of scheduling its flights, or a neural network with millions of weights that can be set independently. All of these examples share two key features:

(1) a finite but exponentially-large space of possible solutions; and

(2) a fast, mechanical way to check whether any claimed solution is “valid.” (For example, do the puzzle pieces now fit together in a rectangle? Does the proposed airline schedule achieve the desired profit? Does the neural network correctly classify the images in a test suite?)

> "We’re asking whether, under the above conditions, there’s a general method to find a valid solution whenever one exists, and which is enormously faster than just trying all the possibilities one by one, from now till the end of the universe, like in Jorge Luis Borges’ Library of Babel."

The paper also discusses caveats, assumptions, limitations, etc. of the concept in an approachable manner. Then it goes off into the depths of theorem and conjecture.