Solving vs. verifying decision problems

Question

I'm trying to understand the hardness of problems (e.g. in cryptography) from the point of view of complexity theory. For the complexity class NP, Wikipedia (11/2023) says

• NP is the set of decision problems solvable in polynomial time by a nondeterministic Turing machine.
• NP is the set of decision problems verifiable in polynomial time by a deterministic Turing machine.

This confuses me because a decision problem has only two possible answers: Yes or No. So a verification (i.e. checking if a given solution is correct) immediately solves the problem. Put differently, solving and verifying a decision problem should be the same.

But if that were really true, then in the above list from Wikipedia both bullet points should refer to the same kind of Turing machine (which in fact they don't), right?

What am I getting wrong?

Answer 1

What is missing is that verifiable in polynomial time means that a witness should exist for a given yes/no answer to verify the solution efficiently. This does not say how easy it is to find the witness. In other words, if you give me an answer-proof pair $(a, \pi)$, then I can efficiently verify it, but I can't necessarily find the $\pi$ efficiently.

Another formulation that makes it easier to understand is in terms of the relation, where there's a notion of the problem instance but also a "witness" for a solution. Concretely. an NP-relation $R \subseteq \mathcal X \times\Pi$. This relation characterizes an NP problem if an algorithm $V$ exists such that an instance $x$ belongs to $R$ if and only if there exists a $\pi$ and $V(x,\pi)= 1$ exists.