# what is the difference between "language" and "certificate" in complexity theory? [duplicate]

Seems like they both are set of strings for which the problem returns "yes" in decision problems.

P class is consists of problems so we can only say a problem is in P. But we sometimes say that a language L is in P. why?

• Your question is a very basic one. Let me direct you towards our reference questions which cover some fundamentals you seem to be missing in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck!
– Raphael
Mar 29, 2016 at 11:19

A (formal) language $L$ is a set of words over some finite alphabet. It can be an infinite set. Generally we're interested in the problem of deciding whether a particular word is in the language or not. For example $L$ can be the set of all Turing machines (encoded as binary strings for example) that halt after at most 100 steps when started with an empty tape, or $L$ can be the set of English words that don't contain the letter 'e'.

A certificate on the other hand is one particular string. When solving the decision problem I talked about above, namely checking whether some word $w$ is in some language $L$, sometimes the problem becomes much simpler if you have some additional information $c_w$. This is often called a certificate for $w \in L$ respectively $w\not \in L$.

For example if $L$ is the set of all graphs that can be colored with at most 3-colors, deciding whether a particular graph $G$ is in this set is NP-complete. But if I already give you a coloring $c_G$ it is very easy to check that it's a valid coloring. The coloring is a certificate for $G\in L$. A coloring has the nice property that it's short, just a couple of bits for each node of the graph. Note that in this case it's not easy to give a (short) certificate for some $G'$ that is not colorable. A very long certificate in this case would be an enumeration of all exponentially many possible 3-colorings of $G'$. Checking that each is not valid is again easy, and since the certificate $c_w$ is so long, the running time of the algorithm with input $G', c_w$ is polynomial as a function of input size.

• This question is a duplicate; you may want to check the other question. If you feel your answer can add something to the material there, please repost it!
– Raphael
Mar 29, 2016 at 11:20
• @Raphael I arrived at this purported duplicate because the only mention of the word "certificate" on the question you've linked was in a site-generated link back to this question. (The question you say this is a duplicate of does not even mention certificates.) I understand that this question is quite basic, but I suggest that you reconsider the marking of this question as a duplicate.
– Kröw
Aug 25, 2022 at 0:10
• @Kröw Hm, the title of the question and its body are very different. For the body, I think the duplicate link is good. Anyway, since this one is ancient, please open a new question about certificates and I'm sure there will be good answers. :) (We could migrate the one from here over, too, if that's helpful.)
– Raphael
Aug 25, 2022 at 11:34