# Why is the certificate version of NP so ubiquitous?

I've noticed that the certificate/verification version of the definition of the class NP is much more popular online than the Turing machine version. In particular, the Wikipedia page has the certificate version stating

NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine.

listed first, and Google's featured result (via Britannica) has this version. This seems to be especially true for explanations aimed at wider audiences such as YouTube videos from popular creators (i.e. not lectures on the subject or course recordings) such as here and here).

Is there a fundamental reason why this appears to be the preferred presentation online?

It's likely due to the simplicity, because if you use the TM definition, which I assume is the non-deterministic TM solving in poly time, now you have to explain what a non-deterministic TM is, how it works, and why it would work to solve such a problem.

Understanding that an NP problem is so because we can check its answer in poly time is much easier to understand for most people.

For a concrete example, you can either explain to someone that for Sudoku

1. It is in NP because given a solution, we can check every group of squares, and every column and row to make sure the solution works.
2. It is in NP because given a sudoku board, we can construct an algorithm for a non-deterministic TM that tries all 1-9 numbers for each empty square, and one of the TMs will have the right answer...and then you have to explain why the correct answer exists in this scheme

So 1. is easier and that's likely why we use that definition.

• Given a problem in NP, in many cases you could hand me, a human being, a solution, and I could check the solution with pen and paper and nothing else, and with no explanation needed. For example the travelling salesman problem, and we solve the problem of visiting all US capitals, all I need to do is add up fifty numbers. On the other hand, nobody has ever built a real non-deterministic Turing machine. May 26, 2022 at 11:03
• @gnasher729 this does not prove the solution is optimal, therefore TSP is not known to be in NP. May 27, 2022 at 9:30
• TSP is in NP: "Is there a tour of length at most K connecting N cities". The optimisation variant is known not to be in NP, because it is not a decision problem, and only decision problems are in NP. May 27, 2022 at 9:44