P = NP since 1950

The computer science problem known as “P = NP?” can be summarized as: is it possible to cope with exponentially many alternatives without using exponentially more time? The usual way of thinking about it is to question whether there is a general technique for quickly finding the right answer without considering a significant fraction of all the possible answers. In this article I consider the idea of considering every possible answer, but using an amount of time that does not increase exponentially as the search space does. The answer for now appears to be that, yes, exponentially larger spaces can be searched with a linear increase in time, thanks to Moore’s law. Moore’s law implies that computing power will double roughly every 1.5 years without costing any more.

Chess has achieved super-human performance mainly by searching deeper. The space is exponential, but we have been going deeper at a linear rate of about one ply (a single move for white or black) every 4.5 years, taking us from about 3 ply to about 15 ply deep since the 1950’s.

Chess has a branching factor of about 2^5 possible moves, which practically speaking can be pruned to about 2^3 moves that are not obviously inferior. In other words, each deeper layer requires 8 times more search, or 3 more doublings in search power. Moore’s law tells us it will take 4.5 years to achieve 3 doublings. The historical improvement from 3 to 15 ply required 36 doublings, which would have taken about 54 years based on hardware improvement alone. In fact in took a little bit less, due to improvements in software. But the accumulated hardware speed-up obviously accounts for most of the progress.

In 54 more years, at 27 moves deep, brute force might find a winning strategy for white, although it would be too complex for humans to use or even appreciate.

In the commercial realm, Orbitz claims to be tackling the traveling salesman problem in the real world using exhaustive search, using low-cost PCs running Linux.

Will it continue? Very likely yes, until P == NP is actually achieved with quantum computing. So, don’t let a big search space get you down. Just work on smarter pruning and be patient.