Garey-Johnson Cartoon Updated
The Famous Cartoon
The 1979 textbook by Michael Garey and David S. Johnson “Computers and Intractability: A Guide to the Theory of NP-Completeness” has been very influential and is one of the most cited books in computer science.
The book famously features a cartoon which depicts a researcher who reports to his boss and justifies why he didn’t succeed in carrying out a given task. With that scenario the cartoon illustrates how the method of NP-completeness can be used to resolve a famous predicament of computer science where for literally thousands of fundamental computational problems one can neither give an efficient algorithm, nor prove that such an algorithms doesn’t exist.
Here is a new and more contemporary version of the cartoon. Do you spot the difference?
Starting with the current 2018 summer term, the new cartoon will be used on lecture slides for the first-year algorithms course at TU Wien.