A decision problem is a problem with a yes or no answer. An NP problem is one where a "yes" answer can be verified quickly if they also give you some proof or "witness" of it. If I say "is there a route that goes through all these cities that's less than 500 miles long", and you answer yes, you can prove that such a route exists by showing me one of these and I can simply check how long the route is. So the problem is in NP because a "yes" answer can be proven or checked quickly.

However, if you say "no, there is no such route", there's not obviously any way to quickly show that. Despite that, the problem is still in NP because to be in NP there only needs to be a quickly-checkable proof of a "yes" answer. If you want a quickly checkable proof of a "no" answer, you need a separate class of problem called co-np.

A problem can also be in np and co-np at the same time, if both "yes" answers and "no" answers can have a proof that can be checked quickly.

In this context we can divide problems into two cases: optimization problems ("find a solution that satisfies P, in a way that has the highest score") and decision problems ("is there a solution that satisfies P, with score >= X" or "find a solution that satisfies P, with score >= X").

Complexity classes like NP are defined only for decision problems, not for optimization problems. NP can be defined either as

* the set of decision problems where, given a solution, you can check it in polynomial time with a deterministic Turing machine, or * the set of decision problems solvable in polynomial type by a non-determistic Turing machine

these two definitions being equivalent.

When someone mentions an optimization problem being in P, NP, or NP-hard, they actually mean the associated decision problem being in P/NP/NP-hard.

While technically incorrect, this is fine when working informally, because you can "translate" between the two in polynomial time.

If I give you an oracle (ie. a magic box) that solves an optimization problem (ie. gives you a solution to P with the highest score) immediately, you can trivially write a polynomial time algorithm that solves the decision problem: call the oracle, check the score of its answer, then compare that with the X value you were given. And vice versa: if I give you an oracle that solves a decision problem immediately (ie. given a value X, gives you a solution satisfying P with score >= X), you can write a polynomial time algorithm that uses the oracle a few times with the right values of X (exponential search then bisection), to find the solution with the highest score.