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

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

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.

## Mr.Wang 8:26 pm

onOctober 21, 2009NP 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.