- 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
