The Quandaries of Quantifying Complexity

My good friend and computer scientest Kyle Burke has recently started a highly interesting blog on his research field: combinatorial game theory. The idea of this field is to use games as a tool for studying issues of complexity. Though his blog is only a month old, some important foundational ideas have begun to rear their heads, one of which I'll explore in this post.

Understanding complexity is important for almost any human endeavor, but defining it in rigorous terms is notoriously difficult. For example, which is the more complicated game, chess or tic-tac-toe? Almost anyone would say chess, but suppose you had a computer that was designed only to play chess. In fact, this computer has no capacity for calculation; it simply has the best move for any given chess position hardwired into its architecture. To get this computer to play tic-tac-toe, you would have to program it to translate each tic-tac-toe position into an analagous chess position, so it could then find the best chess move and translate this move back into tic-tac-toe. This computer would certainly find chess an easier game to play.

Computer scientists have a way around this paradox: instead of looking at individual games or problems, they look at classes of problems. Each problem in the class has a certain size, and they look at how complexity increases in relation to size.

For example, you could easily imagine playing tic-tac-toe on boards of various sizes. Computer scientists can analyze how the complexity of tic-tac-toe varies with the size of the board. (Chess, on the other hand, doesn't generalize as easily to larger sizes, which makes it difficult to talk about its complexity.)

Unfortunately, if we are faced with a real-world issue (such as how to provide for the needs of a large population), we will want to know the complexity of the specific problem at hand, not how the complexity might theoretically scale with problem size. Part of the reason that complexity issues are so often ignored (to the detriment of many well-meaning policies and programs) is that defining and quantifying complexity is so unavoidably slippery.

Further reading