What is the difference between NP and NP Complete problems?

- a problem in NP means that it can be solved in polynomial time with a non-deterministic turing machine

- a problem that is NP-hard means that all problems in NP are "easier" than this problem

- a problem that is NP-complete means that it is in NP and it is NP-hard

example - Hamiltonian path in a graph:

The problem is: given a graph as input, an algorithm must say whether there is a hamiltonian path in it or not.

in NP: here is an algorithm that works in polynomial time on a non-deterministic turing machine:

guess a path in the graph. Check that it is really a hamiltonian path.

NP-hard: we use reduction from a problem that is NP-comlete (SAT for example). Given an input for the other problem we construct a graph for the hamiltonian-path problem. The graph should have a path iff the original problem should return "true".

Therefore, if there is an algorithm that executes in polynomial time, we solve all the problems in NP in polynomial time.j