Computational Complexity, Part III

I was being a bit hyperbolic when I said that if P and NP were equivalent, then all our problems are solved. There are a lot of very important problems in NP that would no longer be effectively unsolvable, but some problems are even harder than NP-complete, and those would not be made any easier by this development.

I touched upon the fact that larger problems require more memory in addition to more time than smaller versions. There are some problems for which we know that the amount of memory required to solve the problem is O(N^k). It may take a very long time to solve the problem, but the amount of memory required is manageable. Problems in this class are said to be in PSPACE.

A good example of a problem in PSPACE is the problem of playing perfect chess on an N by N board. At each turn, there are only a finite number of moves that you can make, based on the pieces you have on the board, the pieces your opponent has on the board, and the limitations of each type of gamepiece. The game could continue for an extremely long time, but at each turn, you need only enough memory to store all your possible moves. The Go endgame is also in PSPACE.

And then there are the problems that are undecidable. For these problems we have no way of figuring out the answer. For example, will my computer program halt? This is an undecidable problem.

Suppose I had a perfect computer that never lost power, never overflowed or underflowed, never ran out of memory, never broke down, etc. If I write a program for this perfect computer, it is not possible to know in advance whether my program will reach the end. (On a real computer, you can guarantee that a program will halt, if for no other reason than extenuating circumstances having nothing to do with the computation! Of course, this doesn't help with evaluating the logic of an algorithm.) Here is an example:

x = 3
do until quitting:
    for a = 1, 2, …, x
        for b = 1, 2, …, x
            for c = 1, 2, …, x
                for i = 3, …, (prime numbers up to) x
                    if (aⁱ + bⁱ == cⁱ)
                        quit
                end for
            end for
        end for
    end for
    x = x+1
end do

This program tests Fermat's last theorem: Are there any integers a, b, c > 0, and prime i > 2, such that aⁱ + bⁱ = cⁱ? The answer is no. Fermat's last theorem has been proved (the proof has stood for about 13 years and no unfixable flaw has yet been found!), but there are other problems similar to this one for which we have no proof. We could reduce one of these problems to a computer program that terminates if the answer is "yes," and does not terminate if the answer is "no." If we had a method that could always figure out whether a program would terminate, then we could use it to solve these problems, just like how we can solve all NP-complete problems if we have a way to solve one.

Unfortunately, it is impossible to determine whether a program will terminate. Here's a proof by contradiction: Suppose we had a program, terminates(p, x), that would figure out whether a program p terminates, given input x. Then, let's say we had another program, evil_program(p), with the following algorithm:

evil_program(p):
    while (true)
        if (terminates(p, p) == false) quit;
    end while

This program causes a contradiction if you call evil_program on itself. Would evil_program(evil_program) terminate or would it keep going? Neither outcome is possible, because evil_program(evil_program) terminates only if evil_program does not terminate. We have created a logical paradox, so we must conclude that our initial premise (the existence of terminates(p, x)) is flawed.

I hope that you have found this discussion of computational complexity as interesting as I have. I recommend a couple of very good websites as supplemental reading. (I drew from many of them as inspiration, particularly for this last installment, because I am not very familiar with PSPACE and undecidable problems.)

For a technical description of NP-completeness, the Wikipedia entry is very informative. They also have a long list of NP-complete problems. For a more informal discussion of these concepts, David Eppstein's page is invaluable. Finally, this chapter from a book on algorithms by Dasgupta, Papadimitriou, and Vazirani is both understandable and fun to read, and gave me the proof for the non-existence of the terminates program.