NP: One that has a non-deterministic, polynomial time solution. (Mind you, it is still polynomial time). The other way to define it is, given a solution (certificate), one can verify correctness of the solution using a deterministic Turing Machine (TM) in polynomial time.
NP-Hard: A hard problem - at least as hard as the the hardest problem known (& unsolvable) so far.
NP-Complete: ( NP ) <intersection> ( NP-Hard ).
NP & NP-Hard are different, and overlap only in certain cases when they are NP-Complete. Many NP-Hard as a result, are not NP-Complete.
No comments:
Post a Comment