Lance Fortnow's Article on Computer Science Problem Featured in NY Times
It's called P vs. NP, and for computer scientists like Lance Fortnow, it's the biggest theoretical problem in computer science.
Despite its real-world implications, most outside of the field have never heard of the challenge.
Nevertheless, Fortnow's article on the subject, which was published in the September issue of Communications of the Association of Computing Machinery, has garnered attention far beyond the field.
Most recently it was featured in a New York Times article — an article that led with the fact that Fortnow's article was downloaded by more than 10 times the usual number of the magazine's readers after just two days online.
"I'm shocked," Fortnow says of the attention.
As a professor of computer science and engineering at Northwestern University's McCormick School of Engineering and Applied Science, Fortnow and his research focus on the problem, which asks whether every algorithmic problem with efficiently verifiable solutions has efficiently computable solution. Here's how Fortnow explains it:
"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 Edmonds 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.)"
So what if P = NP? Computing challenges would suddenly become quick and simple. Optimization problems would become easy, and everything would be much more efficient. Transportation would be scheduled optimally to move people and goods around quicker and cheaper. Manufacturers could improve their production to increase speed and create less waste.
But solving the P vs. NP has confounded computer scientists for decades. Back in 2000, the Clay Mathematics Institute offered $1 million for the solution. The offer still stands.
"It's a question of, How do you deal with hard problems?" Fortnow says. "How do you address problems you can't solve directly? I teach this in my undergraduate classes. We don't say, this problem is hard, it can't be solved. We say, this problem is hard, so what are we going to do with it?"
Some might be getting close. A University of Chicago professor is approaching the problem using algebraic geometry, but a solution could take decades or more.
"I used to hope for a mathematical proof before I died," Fortnow says. "Now I'm less confident, though it might be solved in a day if someone comes up with the right approach."
So what does Fortnow take from the popularity of his article? Impetus to pen a book on the matter, perhaps, or at least the knowledge that he brought computer science to a wider audience.
"Hopefully it will inspire people to consider research in computer science," he says. "That would be the best scenario."
To read Fortnow's article, click here.