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

  • PhD completed by Anaïs Villedieu

    PhD completed by Anaïs Villedieu

    2023-07-24
    Anaïs Villedieu successfully defended her PhD thesis “Engineering Human-in-the-loop Graph Drawing Algorithms” on July 24, 2023. Congratulations, Dr. Villedieu! Anaïs …Read More »
  • PhD completed by Andre Schidler

    PhD completed by Andre Schidler

    2023-05-31
    Congratulations to André Schidler, who successfully defended his PhD thesis "Scalability for SAT-based combinatorial problem solving" today.   Thanks to …Read More »
  • PhD completed by Vaidyanathan P.R.

    PhD completed by Vaidyanathan P.R.

    2023-05-12
    Congratulations to Vaidyanathan P.R., who successfully defended his PhD thesis Scalable Bayesian Network Structure Learning using SAT-based Methods today. Thanks …Read More »
  • PhD completed by Nikolaus Frohner

    PhD completed by Nikolaus Frohner

    2023-05-11
    Congratulations to Nikolaus Frohner, who successfully defended his PhD thesis "Advancing State Space Search for Static and Dynamic Optimization by …Read More »
  • Best paper award at IEEE PacificVis 2023

    Best paper award at IEEE PacificVis 2023

    2023-04-22
    Markus Wallinger, Alexander Dobler, and Martin Nöllenburg received the Best Paper Award for their paper LinSets.zip: Compressing Linear Set Diagrams …Read More »

News archive

All news for 2015, 2016, 2017, 2018, 2019, 2020, 2021 and 2022.
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.