Saturday, March 08, 2003


Simulation and Its Discontents, Part II

So what's wrong with simulation? First, allow me to take a short detour through graduate-level computational complexity, for those of you smart or lucky enough to not go to computer science grad school. There's a class of problems known as NP, which among other attributes, are extremely computationally expensive to solve, using the best known current method (technically, it takes exponential time to solve them, e.g. for every additional input, the time it takes to solve will double). For large inputs, this is impractical. The best known instance of this is the so-called Travelling Salesman Problem (also known as TSP), in which you try to determine the shortest possible path visiting a number of cities once each.

A lesser known attribute of NP is something called the certificate, which is the answer. A certificate for TSP would be something like "Start in Boston, then go to Providence, then go to New York...". Now while it takes exponential time to find a certificate, a given certificate can be checked in polynomial time (which is usually much, much faster). So, if I handed you an answer for TSP and claimed that it was less than 10000 miles, you could check that by simply walking through the list and adding up the distance. Done.

Simulations, however, by definition can have no certificate. They are (generally) in another class called P-Space. There's no shortcut: to get the answer, you must run the entire program from beginning to end. This is the great weakness of simulations: once I get to the end, I have no convincing proof that my answer is correct, other than the entire run of the program. Put another way, there's no compression of the information. This makes it very easy for those opposed to the outcomes of a simulation (e.g., that a new highway will not improve traffic congestion) to simply dismiss the results.