## NP-Complete problem’s Fun.

Recently i had a discussion with my old college friends on Facebook, and we were posting technical questions that would tickle our brain and help us re-live our college days…

Following was my questions…. Posting it here as it might help the reader of my blog understand one beautiful characteristic of NP Complete problem.

**Q: There are sets of problems, if i we find solution to one of them then we have solutions to all of them, what is the technical name for these problem class?**

There were multiple reply to it, one interesting one was design pattern…. Then the discussion went into clue (TSP) then we arrived at NP-Complete. Then the discussion went further into exponential Big-O time etc… But I later sensed the wow factor the question had was gone as part of our discussions… I did some study to bring back the wow factor the question had. Following was my reply…

[Reply]

The real WOW factor that I had when I read these things in my college days is, “WHAT!!!!!! If I solve (in computer terms produce an effective Algo) for one of the problem in the problem class I can solve all of them? How nerdy would be the finder of such things be??? ” [I doubt if I have this level of curiosity now:) ]

*These are the current characteristics of NP-Complete problems.*

*1) There is no known ALGO which can complete in polynomial time (in computational terms no BEST solutions ie. Best in the order of N….- >LogN *

*2) If we can find solution (Algo –reasonable solution) to one of them you can solve All of them. (the real YAHOO!!! is here!!!}*

It means a one NP-Complete problem can be transformed into another NP Complete problem in a polynomial time, isn’t that great. That is what the theorem claims.

It means if I solve one of the NP complete problems I can solve all from the NP Complete list…. http://en.wikipedia.org/wiki/List_of_NP-complete_problems . In other words if I solve the NP complete version of Traveling Sales Person problem I can transform all the other NP complete problems to traveling sales person problem and solve it in polynomial time.

i.e … TSP == Solvable in polynomial time. Then I have solution (best Algo) to NP Complete version of Hamilton Path problem , which no one else has…. Because Hamilton Cycle Solution = Transform2TSP (Hamilton Cycle) (polynomial time) + Solve TSP = (Hence NP complete Hamilton cycle problem is solved in polynomial time) …

To state it practically….if the Subset problem that vels mentioned is NP Complete then it can be converted to the corresponding TSP version in polynomial time and viseversa. (Yahoo!!!!!!!) . And if i have an solution (again a solution for computer programmers is good algo to solve the problem) to the subset problem i can solve TSP…

To make it more fun… see this picture

leave a comment