Different Types of Complexity Classes :-
P Type: They can be solved by Deterministic Turing Machine in Polynomial time.
NP Type: They can be solved by Non Deterministic Turing Machine in Polynomial time.
NP Complete: Hardest Problems set in NP Type. (Any NP can be converted to another NP in polynomial time)
NP Hard: Any NP complete problem can be reduced to NP Hard Problem in Polynomial time. So, at least as hard as any NP complete problem.
Note:--
NP Hard are either NP complete or those kind of problems which are even harder than NP type. So It can be above NP also.
No comments:
Post a Comment