New proof unlocks answer to the P versus NP problem—maybe

By Matt Ford

A paper that leaked onto the Web late last week claims to have solved one of the great modern problems in mathematics and computer science. Vinay Deolalikar, a principle research scientist at HP labs, has published a first draft of what he claims is a proof that P != NP. Unlike someone playing minesweeper in their parent’s basement, Dr. Deolalikar has some serious credentials, having made inroads into related computational complexity problems. His history has made people take notice of this grand announcement.

In computational complexity theory, P and NP are two classes of problems. P is the class of problems that a deterministic Turing machine can solve in polynomial time. In more useful terms, this means that any P problem can be solved in less than c*nk steps. c and k are constants, independent of the input size, n—this means that the amount of time or space needed to solve a P problem are some polynomial function of the input.

NP, on the other hand, are problems that can be solved on nondeterministic Turing machines (which we don’t know how to make) in polynomial time. Only the solution to a NP problem can be verified on a deterministic Turing machine in polynomial time. Solving them on a deterministic Turing machine generally involves super-polynomial runtimes, e.g. c*kn. Again, c and k are constants independent of the input size, n, meaning that the number of steps required increases exponentially with the input size.

The question addressed in the proof is the exact relationship between the classes P and NP—are they one and the same (implying P=NP), or do they represent logically different classes of problems (P != NP)?

The proof’s conclusion, that P != NP, isn’t a terribly shocking result; many people had assumed this for years. Yet, to date, no one has been able to prove it and withstand peer-review. The proof won’t shatter the field of computation complexity, or our understanding of what is computable by a machine. If it’s correct, it merely demonstrates what many have thought to be the case for some time… Read More>>


Comments are closed.

%d bloggers like this: