Certificates and NP?

Question

My book says a language is in NP if it can polynomially verified if a string belongs to the language with a certificate. It puts no restrictions on what the certificate can be.

For instance, for SAT, the certificate could simply be be the assignment values. We just sub them in and see if it satisfies the expression.

But can't we just let the certificate by whether the string belongs or not? So for instance, for SAT, instead of the certificate being the assignment values, we let it be whether the expression is satisfiable or not. In other words, the certificate is the "answer".

If we let the certificate be this, can't be verify any string in polynomial time? Constant in fact, because we would just be returning the certificate itself, since the certificate is the "answer" (whether the string is part of the language or not)

Answer 1

You must be able to verify in deterministic polynomial time that the certificate is correct.

If your certificate for SAT is a truth assignment, you can verify that it's a satisfying assignment in deterministic polynomial time, by substituting the truth values of the variables and simplifying the expression. However, if your certificate was just "It's satisfiable, honest!", then you would only be able to verify that if you could solve SAT in P, which you probably can't. The certificate has to be a proof that the string is in the language, not just a claim that it is.

Indeed, if it was enough to just claim that the string is in the language, then every language would be in NP! For example, the certificate version of the halting problem would be just the set of all strings "$\langle M, w\rangle\text{ It halts, honest!}$" for all machines $M$ and inputs $w$ such that $M(w)$ halts, and all strings "$\langle M,w\rangle\text{ This one loops - too bad!}$" for all machines $M$ and inputs $w$ such that $M(w)$ doesn't halt.