So I admit it. I am a geek. The beauty of the numbers has long fascinated me. It is one of the reasons I wound up getting an advanced degree in physics. I considered engineering, mathematics, and even art as my college major, but physics won out on the fun factor. Engineering was too pedestrian, Art too risky, and the mathematicians I saw really didn’t look like they were having a good time. I wound up getting a masters degree in nuclear physics. but I am not doing anything with it these days. If I can say one thing about getting a masters degree (which probably applies to any masters degree, not just physics) is that graduate school taught me to think, to use the tools my undergraduate degree gave me. Physics taught me to look at the big picture as many solutions to Physics problems apply to a great many very different types of problems.
But I digress, I really still am a beauty of the numbers gal.
So one problem, which is kind of like the problem of all problems, is the P verses NP problem. What is P verses NP? In a nutshell, the big question is whether P = NP or P ≠NP; if P = NP then every problem has a efficient solution and we can find it efficiently. One might postulate all problems are solvable in an infinite amount of time, but what good is that? Only God, perhaps, has an infinite amount of time to solve problems; in the real world problems need to be solved in a finite and reasonable amount of time. The amount of time is the crux of P verses NP. Are problems really as complex as they appear? Is the only solution brute force over an infinite amount of time?
By way of example, consider we have a large number of wedding guests we need to seat at tables at the reception. We might want to pair them up into groups of two people who like each other, so that no one is lonely. In 1965 a guy named Jack Edmonds developed an efficient algorithm to solve this particular problem, and having an efficient algorithm means, among other things, you can feed it to a computer and solve the problem in a reasonable amount of time. Jack Edmonds pioneered the lingo for P verses NP. Problems with efficient solutions are the “P”, in P verses NP. This particular problem is called the “matching problem.”
But there are many other ways to seat our large number of wedding guests that are by far more difficult to solve. Suppose we want to make groups of three wedding guests who like each other, OR large groups of wedding guests who like each other, OR we want to seat guests around a round table such that guests, who can’t stand each other, are not seated next to each other, OR group three couples at the wedding with other couples in a mutually agreeable triads, OR the evil converse social science experiment where only guests who can’t stand each other are grouped together in one way or another (hey, maybe the wedding planner has a thing for the groom). All the problems that have efficient, verifiable solutions are “NP”.
So if P = NP then every problem has an efficiently verifiable solution AND we can find it efficiently. On the technical side, even if this statement is true, we still may not have the algorithm to efficiently solve a given problem. The P verses NP problem is an abstraction, therefore just because we may do something doesn’t necessary mean that we can…
Naturally this question has ramifications well beyond computing algorithms, such as mathematical proofs, encryption, DNA sequencing etc.
Why think about it at all? The P verses NP problem is one of the seven Clay Mathematics Institute Millennium Prize problems; solving it is worth $1,000,000. Not a bad chunk of change, but also realize proving P = NP might solve other Millennium Prize problems as well, each worth $1,000,000. However you should know that many theorists believe P ≠NP. Don’t get your hopes up. 