Thoughts on P vs NP

An NP problem

See P vs NP - further reading for a list of books related to this subject

Suppose that you were very rich, but owed a large amount of money to a colleague. Naturally you don't keep your money as cash, rather it is in the form of a large number (say M) of investment bonds. You and your colleague have agreed that you can pay the debt with these bonds and have agreed on the value of each one, and you find you have plenty enough to cover the debt. However, the values of the bonds are all different, and so the question is can you find a set of them that add up to exactly the right amount. Naturally your colleague won't accept less than the debt, and you don't want to pay even one cent more (you wouldn't be rich if you started doing things like that!). Once you've found the correct set you know its right, but finding whether such a set exists is likely to take a long time, involving a lot of backtracking - taking 2M steps.
This problem and SAT below are what is known as NP-complete problems. This means that any other NP problem can be made equivalent to it with only a number of steps which is polynomial in M
Now if you had a device which would tell you at each stage whether your selection so far could lead to a solution, then that would make it a lot easier - it would only take about M steps. Such a device is called a non-deterministic computer. Problems, such as the above which can be solved by a non-deterministic computer in a number of steps which is a polynomial in some measure M of the size of the problem are said to be in the complexity class NP (nondeterministic polynomial).

The Satisfiability problem

Another example of an NP problem is the Satisfiability problem SAT. Here you are given a boolean function F of M variables x1, x2 .. xM. F can involve the operators and, or and not. The problem is to find values for these variables which give the function F the value true. For example we might have
  F=( x1 or x2 or x3 or x4) and (x1 or not x3 or x4) and (not x2 or not x3 or not x4) and (not x1 or x2 or x3)
It's not too hard in this case to find x1=true, x2=false x3=true x4=false which satisfies F(x1,x2,x3,x4)=true, but if you have many more variables it can be much harder.

$1000000

Clay mathematics institute prize problems

Although it seems clear that a non-deterministic computer would be more powerful that a normal, deterministic computer, in that there doesn't seem to be any possibility of solving problems such as the above in polynomial time on a normal computer (complexity class P) , one can't be sure. Maybe someone one day will come up with a really clever algorithm. People have been trying to prove NP≠P for some time, but so far have not succeeded. In fact this is one of the problems for which the Clay mathematics institute is offering a million dollars for a solution.

Undecidable?

One possibility that has been put forward in that the P vs NP question may be undecidable, in the same way as the continuum problem. I think this is a red herring. Undecidabilty of a statement means that it can't be proved from the axioms of number theory (or whatever theory we are working in), and that in some mathematical models of the theory it is true, and in others it is false. However, we aren't restricted to a narrow set of axioms when proving a result about computers, we can use anything we know to be true. We aren't really interested in whether or not NP≠P is true when we use some weird non-standard model of the integers, but only when we use the standard integers - can you imagine a program with loops nested to a depth of a non-standard integer?

Diagonalization...

An example of a diagonalization proof is the proof that for certain games it takes an exponential time to find which player has a winning position, as described on the
Fast computers and Games page
So how might you go about proving such a thing. Well, one way to prove lower bounds in the time taken to solve problems is known as diagonalization. The idea here is to imagine a list of all programs of the type you are interested in. Then each program can be considered in two ways, either by what it does, or by it's number in the list. This indexing system can then be used to match statements about programs to the programs themselves. If we assume the existence of a program which does better than the constraint we are looking at then we can use this matching to derive a contradiction

... won't work

Having introduced diagonalization to you, I now have to tell you that it won't work in trying to prove NP≠P. Consider a computer together with what is called an oracle, which tells you whether an input belongs to a specified set or not. It is then possible to define complexity classes for such a computer, so we can have P or NP relative to an oracle. Diagonalization proofs would carry over from a normal computer to a computer with an oracle, so if there was such a proof then you would expect NP≠P for all oracles. However it has been shown that relative to some oracles P=NP whereas relative to others NP≠P.

My ideas

In the SAT problem we have to satisfy a boolean formula F(x1..xM). We can make this into a game: two players each have a formula F1(x1..xM) and F2(x1..xM) with starting values of x1..xM which make both of them false. The players then take it in turns to alter the value of one of the variables with the aim of making their formula true while the other player's remains false. What we want is a program which, given the starting position, will find which player has a forced win. As mentioned in the Fast computers and Games page, this is known take time exponential in M. However, I can't help thinking that the similarity to the SAT problem must count for something and that if we assumed that there were a polynomial algorithm for SAT, then this could be used to derive a sub-exponential algorithm for the game problem.

Statement by statement

What will not work is trying to solve the game problem by stringing together solutions of SAT. It is known that the game problem takes exponential time even for nondeterministic computers. Rather, we have to assume that there is a specific program which solves SAT for a formula F1 in polynomial time, made up of individual program statements for a specific processor. My idea is to replace each statement with a program acting on F1 and F2. In particular it might solve SAT for F2 or for some function of F1 and F2 (remember we are assuming that this can be done in polynomial time). The hope that it is somehow possible for the main program to be converted into one which solve the game problem. Well it's just an idea... If I was really sure it was going to work then I wouldn't tell everyone would I?