**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

<< Home