2009 TheStatusOfPvNP

• (Fortnow, 2009) ⇒ Lance Fortnow. (2009). “The Status of the P versus NP Problem.” In: Communications of the ACM, 52(9). doi:10.1145/1562164.1562186

Subject Headings: P versus NP Question, NP Complete Task, Theoretical Computing Science Research Question.

Notes

• Related to another similarly entitled paper "The Status of the P versus NP Problem."

Quotes

Abstract

• It's one of the fundamental mathematical problems of our time, and its importance grows with the rise of powerful computers.

What is the P versus NP Problem?

Suppose we have a large group of students that we need to pair up to work on projects. We know which students are compatible with each other and we want to put them in compatible groups of two. We could search all possible pairings but even for 40 students we would have more than 300 billion trillion possible pairings.

In 1965, Jack Edmonds12 gave an efficient algorithm to solve this matching problem and suggested a formal definition of “efficient computation” (runs in time a fixed polynomial of the input size). The class of problems with efficient solutions would later become known as P for “Polynomial Time”.

But many related problems do not seem to have such an efficient algorithm. What if we wanted to make groups of three students with each pair of students in each group compatible (Partition into Triangles)? What if we wanted to find a large group of students all of whom are compatible with each other (Clique)? What if we wanted to sit students around a large round table with no incompatible students sitting next to each other (Hamiltonian Cycle)? What if we put the students into three groups so that each student is in the same group with only his or her compatibles (3-Coloring)?

All these problems have a similar favor: Given a potential solution, for example, a seating chart for the round table, we can validate that solution efficiently. The collection of problems that have efficiently verifiable solutions is known as NP (for "Nondeterministic Polynomial-Time," if you have to ask).

So P = NP means that for every problem that has an efficiently verifiable solution, we can find that solution efficiently as well.

 We call the very hardest NP problems (which include Partition into Triangles, Clique, Hamiltonian Cycle and 3-Coloring) "NP-complete," that is, given an efficient algorithm for one of them, we can find an efficient algorithm for all of them and in fact any problem in NP. Steve Cook, Leonid Levin, and Richard Karp10, 24, 27 developed the initial theory of NP-completeness that generated multiple ACM Turing Awards.

In the 1970s, theoretical computer scientists showed hundreds more problems NP-complete (see Garey and Johnson16). An efficient solution to any NP-complete problem would imply P = NP and an efficient solution to every NP-complete problem.

Most computer scientists quickly came to believe P ≠ NP and trying to prove it quickly became the single most important question in all of theoretical computer science and one of the most important in all of mathematics. Soon the P versus NP problem became an important computational issue in nearly every scientific discipline.

---

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2009 TheStatusOfPvNP	Lance Fortnow			The Status of the P versus NP Problem		Communications of the ACM		10.1145/1562164.1562186		2009