Thursday, March 29, 2007

NP Complete

I in one of my moods realized all real life problems are NP-Complete problems and the only way to solve them is to use techniques that are known to work with NP Complete problems:
1. Reduction: Reduce it to NP problem with known heuristic
2. Heuristic: Solve using what works most of the time
3. Approximation: Approximate the solution

If we realized that there is no perfect solution or the perfect solution to the problem is not worth the cost, we would be much faster in making decisions and moving on to another NP-Problem. If we are stuck into not accepting the complexity as inherently insolvable and persist on solving it for perfection, in more cases than less we would not get anywhere.

Formal Defintion from Wikipedia

A decision problem C is NP-complete if it is complete for NP, meaning that:

  1. it is in NP and
  2. it is NP-hard, i.e. every other problem in NP is reducible to it.

"Reducible" here means that for every problem L, there is a polynomial-time many-one reduction, a deterministic algorithm which transforms instances l ∈ L into instances c ∈ C, such that the answer to c is YES if and only if the answer to l is YES. To prove that an NP problem A is in fact an NP-complete problem it is sufficient to show that an already known NP-complete problem reduces to A.


No comments: