Thursday, August 9, 2007

P and NP Complete

There is a set of terms on computational math called P and NP. NP-complete problems are non-deterministic in polynomial time, or basically they are damn hard to actually prove the correct solution. Fuzzy logic, genetic algorithms, and other fun sorts of math must be used to approximate the solutions. For example, there is a problem known as the Traveling Salesman Problem (TSP). It sounds very simple: "Given a number of cities and the costs of traveling from any city to any other city, what is the cheapest round-trip route that visits each city exactly once and then returns to the starting city?"
The math in this problem is resolved readily into a solution space of (n-1)!/2 where n is the number of cities. This seems easy to brute force, after all if there are 3 cities then n=3 and the solution space is 1, if there are 4 cities then the solution space is 3. Not too hard, right? If there are 5 cities then the solution space is 12. A slightly larger set. That is the catch, if the number of cities is 6 then solution space is 60. For an example as to why this gets hard to solve, at 10 cities the solution space becomes 181,440.
The reason for all of this, besides the fact that I sat through classes on this crap, is that a scientist is using this problem as a possible trial for using photons to perform computations. A few years ago someone proposed using DNA, however individual DNA are too big to actually solve complex problems, because as you can see from above, you need incredibly large numbers to solve this problems. In the case of n=10 you would need 181,440 pieces of DNA, which is not too bad. However, when you get into larger and more realistic numbers, it becomes physically too large. For example, n=100 requires 4.7E+155 (for the non-math folks that is 47 with 154 0s behind which is a really really big number. Photons are considerably smaller then DNA, in fact they are so small they have essentially no mass but are merely sized by the energy they carry. A photon of visible light possesses 4E-19 Joules. 1 Joule = 1 kg *m^2/s^2. The energy is related to the speed of the mass moving in other words, 1 J also is equal to 1 Watt-sec (recall we pay for power by kilowatt-hour). So to solve a TSP problem where n=100 would utilize 6.72E+137 kilowatt-hours. At current Entergy rates in MS of 1kWh costing $0.007365 (less then $0.01) it would cost $4.95E+135, or more money then you can imagine.
Ok, I admit it, I am a huge geek sometimes!

Thesis update: Onto the conclusions and working page 62 at the end of the day. Still have conclusions, future work, and appendices to do.