> Strictly speaking, NP isn’t so much about the finding of solutions, just the verification of their correctness.

Because nitpicking is fun, I'll add my contribution and say that the traditional definition of NP is actually about the finding of solutions, and is the etymology of the phrase "non deterministic polynomial time". That is, a non deterministic machine (one that could magically search multiple states at once) can find a solution in polynomial time.

Of course, since our non deterministic algorithm could just be the enumerate all witnesses, and verify them, then the two definitions are equivalent, except for the verification-based one being much more intuitive.