How to explain NP-hardness and NP-completeness to students

manpreet Best Answer 2 years ago

Computer science is becoming more and more important for mathematicians nowadays. Terms like big data, algorithm, artificial intelligence and others are frequently on the news. Many mathematical problems are tackled via computer scientific methods because many problems cannot be (efficiently) solved by a human being in practice.

Many such problems, like the knapsack problem can be nicely illustrated and are easily accessible for students. However, there are problems (such as the knapsack problem again) which even modern computers struggle to solve in acceptable time for large inputs. When talking about a problem's complexity we will quickly arrive at terms like NP-hard and NP-complete. As these are somewhat abstract concepts I was wondering how these could be explained to students such that they become familiar with the terminology and begin to understand the difference in the complexity classes.

Admittedly, students will find it easy to believe that computers will take longer to solve a given problem if the input size grows. However, this is also true for problems which can be solved in polynomial time on a deterministic machine and completely misses the focus on NP-hardness and NP-completeness.