1
$\begingroup$

I'm a computer science student and I'm having some problem understanding the verifier based definition of NP problems.

The definition says that a problem is in NP if can be verified in polynomial time by a deterministic Turing machine, given a "certificate".

But what happens, if the certificate is exactly the problem solution? It's only a bit, and it's obviously polynomially limited by the input size, and it's obviously verifiable in constant, thus polynomial time.

In other words, i define the certificate as the output of the problem for a given input and the verifier will only verify that its input will be a bit of value 1.

Therefore, each decision problem would belong to NP.

  • 2
    Your definition is like a Turing machine that says yes to everything -- does that render every problem decidable?2011-07-05

2 Answers 2