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?


1 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.

  • $\begingroup$ Okay, thank you. Indeed, I didn't know the concept of a witness. Probably I have to study that first before I will really understand your answer. $\endgroup$
    – maya
    Nov 17 at 10:34
  • $\begingroup$ I think I got it. That was the missing piece. Thanks again. $\endgroup$
    – maya
    Nov 17 at 13:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.