P versus NP – the Holy Grail of Computer Science
Frank Ford
In 1971, Steven Cook stated the P versus NP problem formally in Proceeding of the Third ACM Symposium on the Theory of Computing, but the roots of this question can be traced to Turing, Church and Gödel. The theory of computational complexity stems from two articles published in 1965. A handwritten letter of 1956 from Gödel to Von Neumann presents the problem. P can be viewed as the class of Yes/No questions which can be solved in a number of steps that is bounded by cxn where x is a measure of the length of the codification of the problem and c and n are constants. NP is the class of problems which have a verifier program which takes a proposed solution to a problem and determines if it is a solution in cxn for a problem of size x as above. Many problems have been shown to be NP-complete. These are problems that are so “hard” that if they are in P, then every NP problem is in P. Some practical problems that are in the NP class include Protein folding and placing of transistors on a silicon chip. We will discuss the history and research directions for this problem and the current opinion of the “solution” announced in August 2010 by Vinay Deolalikar of HP Research Labs, Palo Alto.
