In an earlier blog post a week ago, I mentioned that there was a possible proof which answered the long-time open CS theory question: does P = NP? The researcher claimed to have shown that P is not equal to NP in a  100 page proof.  The proof used complexity concepts that I am just not familiar with (yet), so I am not qualified to judge the proof. However, there are a few researchers around the world who are and it appears that, generally speaking, the proof probably won’t hold up. This isn’t to say that there aren’t valuable findings in the paper, there are, but it doesn’t show that P!=NP.

There are two blogs that have a great coverage of this topic and I suggest reading them:

Dick Lipton’s Blog – You should read the post titled “The P!=NP Proof is One Week Old”. He is a professor at Georgia Tech, one of the best CS theory groups in the country.

Scott Aaronson’s Blog – I suggest reading the post “Eight Signs a claimed P!=NP Proof is Wrong”. His other posts on the subject are very good, as well, including his most recent one about hackers. Scott is a professor at MIT.

Lance Fortnow and Bill Gasarch’s Blog –  Lance made a great post on the problem. He is a professor in my department here at Northwestern.

This summer, I am in a reading group working through the book Complex Adaptive Systems. I don’t have the book yet but a PDF of the first two chapters and I thought I would post my thoughts here before I go to the talk this afternoon.

I was originally a big fan of complex systems. I took a few courses at Michigan on complex systems and I’m very familiar with statistical techniques for running simulations.  I even have a sample NetLogo widget on my website somewhere of a theoretical model from my adviser.  Running simulations is kind of exciting and sexy – you usually see graphics of how agents in a system interact and plot out the results.  Then, using stats and inference you can make awesome claims about how the system works and try to infer how this relates to things in the real universe.  This is cool and fun and what made me interested in going into academia.

But then I started my PhD program in the theory department at Northwestern. In theory, we try to make much grander claims: we want to show that something is true or false in all cases or for wide ranges of classes, not just a specific instance.  For example, we want to show certain classes of algorithms can be computed in a certain amount of time. As long as we can show an algorithm is in that class of problems, then we instantly know something about it.  Theoretical findings are powerful but hard to reach, they require extensive mathematical proofs and a great deal of intellectual and logical rigor.

Simulation is useful when you’re using it to compare a theoretical finding against some form of empirical data.   In other words, you’re given some actual real world data points.  You can simulate the theoretical models and show that the data fits your theory.   Verifying theory is important however I contend it is not as powerful of a finding as the theoretical result itself.

Where do complex systems come into this? The authors of the aforementioned book argue that some systems are too complex: we can’t break them down into their components. Therefore, this implies that they argue that theoretical results cannot be found for these systems! Perhaps the systems are too complex; there are too many of what accountants call “intangibles”, things that have value but cannot be counted as assets.  I am not yet convinced of this line of argument; theoreticians should seek to develop mathematical models and tools precisely to model these cases, such that we can develop a better understanding of how our world is classified.