Complexity Classes (P, NP) vs Language Hierarchies (REC, RE) NOTE: The statement of this question has a LOT of misconceptions.



Is there any relation between the Complexity Classes (like P or NP) and Language hierarchies (like REC or RE) ?


  Form what I understand: (easy things are the things that can be done in polynomial time span, as opposed to tough things. Tough things require exponential time span or even infinite time to finish).


P

These are the set of problems which can be easily solved. If multiple answers exist, then all those answers can be easily found.

NP

These are the set of problems, for which a tentative answer can be easily verified. Some of these problems can even be easily solved. Others are tough to solve but either way, given a tentative solution, that can be easily verified.

For those which can be easily solved, fall under the P class. Hence P &lt;= NP. The equal sign is something scientists are still working on.

These problems can be solved easily on a non-deterministic Turing Machine. Unfortunately, such a machine does not exist. The real deterministic Turin Machines (our laptops) cant guarantee how much time it would take to solve such a problem. it might even hang.

REC

These are the set of strings (a language) which belong to one family of strings. The family is called The Grammar. Given a Grammar and a string, if we can easily tell whether the string is member of the family, then the family is REC family.

RE

These are an even broader set of strings, which belong to an even broader family. Some of the members of this family are REC, but some are not. That is, given a Grammar and a string, we may or may not easily tell whether the string is a member or not. If we are able, then the family is REC, if we are not, then it is RE family.

Membership in RE family cannot be easily verified but, given such a Grammar, all the members can be easily listed-out. Hence the name- recursively enumerable.


  Now, Question: both (P/NP) and (REC/RE) seem similar. I know they are not the same. One is problem, another is language. But is there any connection between the two?


Also, From what I understand, is there anything wrong in my understanding? I mean certainly there must be things missing. But for the part which is not-missing, is there anything wrong?
All the classes you mention are classes of languages, formally, even if P and NP are often discussed in different (more sloppy?) terms. Note that terminology revolving around decision problems is equivalent to formal languages; the decision is always whether a word is in the given language, i.e. the problem is to solve the word problem.

What you need to do is go back to the formal definitions. Summarising:


$\mathrm{RE}$ contains languages which are accepted by any TM.
$\mathrm{REC}$ contains all languages which are decided by any TM.
$\mathrm{NP}$ contains all languages which are accepted by any polynomial-time TM.
$\mathrm{P}$ contains all languages which are decided by any polynomial-time and deterministic TM.


It's already quite clear from the definitions that we have

$\qquad\displaystyle \mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{REC} \subseteq \mathrm{RE}$.

So, essentially, computability and complexity theory deal with the same kind of questions: which kinds of problems can I solve with which type of machine?

In fact, the famous Complexity Zoo diagram (via the companion the wiki) displays "computability", "complexity" and "Chomsky" classes in a single inclusion hierarchy -- because they all use the same formalism.

I recommend you check out some of our reference questions on computability and complexity theory; you'll the similarities.