Group I - P vs NP: a Clay Millennium Problem with Economic Flavor
The Problem Statement P = NP? P vs. NP is perhaps one of the biggest open problems in computer science and mathematics but what is P vs NP?. The following question of interest to people working with computer science and mathematics in: Can every solved problem whose answer can be checked quickly by a computer also be quickly solved by a computer? P and NP could be defined as the two types of maths problems referred to: P problems are fast for computers to solve, and so are considered "easy". NP problems are fast (and so "easy") for a computer to check, but are not necessarily easy to solve. But so far, no one’s been able to decisively answer the question one way or the other. Frequently called the most important outstanding question in theoretical computer science, the equivalency of P and NP is one of the seven problems that the Clay Mathematics Institute will give you a million dollars for proving — or disproving.
Background
In 1956, Kurt Gödel wrote a letter to John von Neumann. In this letter, Gödel asked whether a certain NP complete problem could be solved in quadratic or linear time. And in 1971, Stephen Cook introduced the precise statement of the P vs. NP problem in the article called “The complexity of theorem proving procedures”.
