what is the difference between NP, NP-HARD,NP-Complete?

Mr.Wang 8:08 pm on October 21, 2009 | Answers: 1    
Tags: difference (18), np, np-complete, np-hard

Rate Knowledge: (2 votes)

 Loading ...

• Mr.Wang 8:26 pm on October 21, 2009
  

  NP stands for "Non-deterministic Polynomial time" and it symbols a class of problems that can be solved in polynomial time on a non-deterministic Turing machine. The key idea to understand is the "non-deterministic" which means that it is the case when more paths of solution could be chosen and at least one path solves it in a polynomial time.

  The problem is how to find the right solution path and whether we can find the deterministic way that could also solve it in polynomial time — marked as P.

  In other words, there is a bunch of problems that could be solved by non-deterministic machine in polynomial time. Apparenly, all problems that could be solved in polynoimal time on deterministic machines also belongs to NP problems (they are subset of them, because non-deterministic machine is somehow more capable).

  For some problems, for which no deterministic solution was found that would find the solution in polynomial time. These problems are marked NP-complete. It is believed (but not proved) that it is not possible to find them, hence the intersection between P and NP-complete is empty.