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?