## Tuesday, February 18, 2014

### Differentiate p np np-hard and np-complete problems

P: A decision problem that can be solved in polynomial time. That is, given an instance of the problem, the answer yes or no can be decided in polynomial time.

NP: A decision problem where instances of the problem for which the answer is yes have proofs that can be verified in polynomial time (We know the answer, and verified the answer takes polynomial time). This means that if someone gives us an instance of the problem and a certificate (sometimes called a witness) to the answer being yes, we can check that it is correct in polynomial time.

NP-complete: An NP problem X for which it is possible to reduce any other NP problem Y to X in polynomial time  (Any NP Problem can reduce to NP-Complete in polynonial time). Intuitively this means that we can solve Y quickly if we know how to solve X quickly.

What makes NP-complete problems important is that if a deterministic polynomial time algorithm can be found to solve one of them, every NP problem is solvable in polynomial time (one problem to rule them all).

NP-hard: Intuitively these are the problems that are even harder than the NP-complete problems. Note that NP-hard problems do not have to be in NP (they do not have to be decision problems). The precise definition here is that a problem X is NP-hard if there is an NP-complete problem Y such that Y is reducible to X in polynomial time (Any NP-Complete problem can reduce to NP-Hard in polynonial time).

But since any NP-complete problem can be reduced to any other NP-complete problem in polynomial time, all NP-complete problems can be reduced to any NP-hard problem in polynomial time. Then if there is a solution to one NP-hard problem in polynomial time, there is a solution to all NP problems in polynomial time.

• P: The complexity class of decision problems that can be solved on a deterministic Turing machine in polynomial time.
• NP: The complexity class of decision problems that can be solved on a non-deterministic Turing machine in polynomial time.