Algorithms and Complexity Group
  • People
  • Research
  • Courses
  • Talks
  • Jobs
  • Contact

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.

 

The Update

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.

The cartoon has been released by Stefan Szeider under the Creative Commons licence 4.0.

 

 

 

 

 

 

 

 

 

 

 

 

News

  • Martin Nöllenburg: promotion to Full Professor

    Martin Nöllenburg: promotion to Full Professor

    2020-12-17
    By December 1st, 2020, our colleague Martin Nöllenburg has been promoted to Full Professor for Graph and Geometric Algorithms.  Martin has …Read More »
  • Martin Kronegger wins the Best Teaching Award 2020

    Martin Kronegger wins the Best Teaching Award 2020

    2020-10-23
    Congratulations to Martin Kronegger who received a Best Teaching Award 2020 from TU Wien. The Algorithms and Complexity group is …Read More »
  • Welcome to our Feodor Lynen Fellow Dr. Manuel Sorge

    Welcome to our Feodor Lynen Fellow Dr. Manuel Sorge

    2020-10-12
    On October 1, 2020, Dr. Manuel Sorge has joined the Algorithms and Complexity group with a prestigious Feodor Lynen postdoc …Read More »
  • TU Wien students excel at the 2020 Graph Drawing Contest

    TU Wien students excel at the 2020 Graph Drawing Contest

    2020-10-01
    The 27th annual Graph Drawing Contest, held (virtually) in conjunction with the 28th International Symposium on Graph Drawing and Network …Read More »
  • Best Paper Award at CP’2020

    Best Paper Award at CP’2020

    2020-09-11
    Tomáš Peitl and Stefan Szeider won the Best Paper Award at the main track of CP'2020, the 26th International Conference on Principles …Read More »

News archive

All news for 2015, 2016, 2017, 2018 and 2019.
TU Wien Informatics
Offenlegung (§25 MedienG) Inhaber der Website ist das Institut für Logic and Computation an der Technischen Universität Wien, 1040 Wien. Die TU Wien distanziert sich von den Inhalten aller extern gelinkten Seiten und übernimmt diesbezüglich keine Haftung. – Disclaimer – Datenschutzerklärung
Log in requires cookies.