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).
These are the set of problems which can be easily solved. If multiple answers exist, then all those answers can be easily found.
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 <= 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.
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
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 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?