1
$\begingroup$

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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – gnasher729
    Commented May 26, 2022 at 11:03
  • $\begingroup$ @gnasher729 this does not prove the solution is optimal, therefore TSP is not known to be in NP. $\endgroup$
    – Criticize SE actions means ban
    Commented May 27, 2022 at 9:30
  • $\begingroup$ 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. $\endgroup$
    – gnasher729
    Commented May 27, 2022 at 9:44

Your Answer

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

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