The “P vs NP” problem is a major open problem in computer science whose solution will likely require deep theoretical insights and complex proofs. Most practitioners in the field will not be solving or even tackling that problem any time soon, but they still all benefit from understanding the background of the question and the problem classes P, NP, and NP-Complete.
Reading¶
Wikipedia has some great articles on the topic:
-
P versus NP problem
— You may want to focus on these sections: the introduction, “Context,” “Harder problems,” “Does P mean ‘easy’?,” “Reasons to believe P ≠ NP,” and “Consequences of solution” -
NP-completeness — Clear, relatively short, and formal.
- To get a sense of the types of problems that fall in the class NP-Complete, check out the List of NP-complete problems. Among other things, Minesweeper is NP-complete!
- The first set of known-NP-complete problems were Karp’s 21 NP-complete problems; Karp came along after Cook proved the very first one (Boolean Satisfiability) in 1971 to prove that these 21 other important problems were also NP-complete by reducing Boolean Satisfiability to each of them.
This set of lecture notes provides a readable summary of most of this, with good examples and descriptions of much of what we cover in class.
Supplemental¶
You may have heard that there is some money on the line here, from me or from others. The Clay Mathematics Institute are the folks who will give you a million dollars if you solve the P vs NP Problem.
In 2002, Bill Gasarch took a poll of CS researchers, collecting opinions about how P vs NP will be resolved. The results are fascinating, because they include not only raw statistics (the majority of those who answered think P ≠ NP) but also many interesting comments from the respondents, such as one who believes that a proof will come from “a young researcher who is not encumbered by too much conventional wisdom about how to attack the problem.” There are some interesting contrary opinions in there, as well.
As mentioned in class: What to do if you need a [fast] algorithm for a problem and you can’t find one. (or: How to not look bad in front of your boss.)
Levitin¶
- Levitin 11.3
And finally, some algorithmic complexity humor:¶
These are pedagogically relevant. Understanding the humor requires a certain level of conceptual understanding.