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 polinomial 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 obviuosly polinomially limited by the input size, and it's obviously verifiable in constant, thus polinomial time.
Therefore, each decision problem would belong to NP.
Where am i wrong?
But what happens, if the certificate is exactly the problem solution? It's only a bit, and it's obviuosly polinomially limited by the input size, and it's obviously verifiable in constant, thus polinomial time.
Why "obviously"? You might have to spend an exponential amount of time verifying the solution, in which case the problem need not be in NP. The point is that, even though the certificate is a single bit for a decision problem, you don't know whether that bit should be zero or one to solve the problem. (If you always did know that, then any decision problem in P or in NP would be solvable in constant time.)