Why is every instance in P also in NP [verifier-based definition]? [closed]

Question

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 8 years ago.

Improve this question

Somewhat related to this question.

The verifier-based definition of NP complexity class says:

NP is the class of languages which are accepted by a deterministic Turing Machine verifier in polynomial time.

All problems in P are considered to be in NP. As explanation, the following is commonly stated:

Given a certificate for a problem in P, we can ignore the certificate and just solve the problem in polynomial time.

A verifier needs to use the certificate and show that the problem can be verified in polynomial time. Why does everyone keep saying ignore the certificate and just solve the problem ? Is solving the problem equivalent to providing a certificate ?

Answer 1

In worrying about whether the verifier "uses" the certificate, you're taking the term "verifier" too literally. A verifier is an algorithm that takes the original problem and some additional information ("a certificate"), and provides the correct answer ("yes" or "no") in polynomial time. We call it a verifier, but that doesn't impute upon it a new "job".

For problems like subset sum, the certificate serves as a useful shortcut- we're given a subset that we just have to check a) adds up to 0 and b) is a subset. But if we already know the problem can be solved in polynomial time, that shortcut becomes unnecessary.