0
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

marked as duplicate by Raphael Mar 29 '16 at 11:20

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ 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! $\endgroup$ – Raphael Mar 29 '16 at 11:19
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Raphael Mar 29 '16 at 11:20

Not the answer you're looking for? Browse other questions tagged or ask your own question.