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

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.

• The title says "young students" but this is not addressed in the body of the question. How "young" is the intention? – Daniel R. Collins May 14 '18 at 12:43
• This question might be more appropriately asked at Computer Science Educators Stack Exchange. – Joel Reyes Noche May 14 '18 at 12:59
• Wikipedia has useful examples. – Jasper May 14 '18 at 21:22
• You may find this question about NP problems from the CS Educators site helpful. – Peter May 14 '18 at 21:30
• Erik Demaine has a lectures on the subject, and even uses Super Mario as an example. The lectures don't reduce it to the simple sentence you're looking for, but may provide some ideas on how to convey it: youtube.com/watch?v=mr1FMrwi6Ew & youtube.com/watch?v=moPtwq_cVH8. (Typically I don't like getting information from videos, but Demaine never seems to have lost his "child mind", and wrote a very good paper on Algorithmic Combinatorial Game Theory. I strongly agree fundamental computer science is as critical as fundamental math!!!) – DukeZhou May 15 '18 at 21:04

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.

This is an important point which is often neglected in more "accessible" accounts of NP completeness. It gets neglected because (charitably) the author cannot assume familiarity with basic complexity theory and particularly big O notation or (realistically) the author is repeating something that they were told by someone else. So we hear about "problems which can be solved/verified quickly," which is a flat lie by any reasonable definition of "quickly" (a stopwatch does not neglect constant factors).

The educator is in a better position here. We presumably have multiple lectures of time to work with, and complexity theory is an important subject anyway. So you can start with something simple, like comparing linear search to binary search. Place strong emphasis on scalability rather than speed. In this example, you could suggest that the processor is more performant with linear access than random access due to locality of reference (to provide concrete differences in constant overhead of the algorithms). Emphasize that we don't care so much about what the hardware is doing, or about how long it takes to compare two elements, etc. All we care about is the overall growth rate. Depending on the level of the class, it is probably a good idea to give the formal definitions of big O and big Theta notation at this point. Regardless, the students should see $$\Theta(n)$$ vs $$\Theta(\log n)$$ and a derivation of those expressions (even if only informal).

You can then progress to something more challenging, like insertion sort vs. quicksort. It is tempting to throw in some examples of recurrence relations and dynamic programming, but this is not essential and can be deferred to a later course. This trains the students on how the big O and big Theta work and how to manipulate them.

Once the students are at an acceptable level of comfort with complexity analysis in general, and big O in particular, you can move on to complexity classes. At this point, you can mostly get away with giving the algebraic definition (i.e. "the term inside the O(...) is a polynomial"). However, one sticking point is defining the "verification" of NP in a way that is both intuitive and correct. Strictly, a decision algorithm is only supposed to output true or false, but verification requires a certificate describing the solution in greater detail. It may be helpful to use deterministic and nondeterministic finite automata as a simpler point of comparison. You might even show the powerset construction to demonstrate that NFAs are potentially a lot "simpler" than the corresponding DFAs, depending on the available class time. For an introductory course, you may be able to just gloss over this definition.

The other issue comes when working with younger students, for example in a high school computer science class. Here, you may not have the time or syllabus to provide a full account of complexity theory, but still want students to walk away with some kind of understanding. In this case, it may be best to start with one of the "classic" NP-complete problems and explain, in simple terms, why it seems to be so difficult to solve. The knapsack problem is one example, but I don't like it for this purpose because it is pseudo-polynomial. Explaining the difference between pseudo-polynomial time and polynomial time is difficult, and can make it look like the knapsack problem is only NP-complete because of a definition (which is not the case). Instead, I would use the traveling salesman problem, for these reasons:

• Its input size is straightforward to define and does not require talking about the "number of bits" of anything.
• It is easy to illustrate with graphs.
• The exponential algorithm is intuitively simple.
• The exponential algorithm is obviously non-scalable.
• The exponential algorithm exhibits noticeable growth even for very small inputs.
• It is a "classic" problem that people may have heard of elsewhere.

Explain that there is a simple exponential algorithm and what that means. After providing a basic TSP definition:

The "obvious" way to solve TSP is to check every possible route and output the best one. But this scales very poorly. When I add one more city, I have to consider every possible placement of that city in every route that I was looking at previously, and that adds up fast! The number of additional routes is proportional to the previous number of routes, so the overall number of routes we need to check goes through the roof almost immediately.

[Show graphical examples for small N, if possible, or alternatively show a graph of an exponential function. You could also describe rabbits or other small animals reproducing exponentially, or any number of other accessible examples. Adapt this to your audience.]

The bolded phrase is a complete (if very brief) definition of exponential growth, but it may be too brief for students to understand. An example or two certainly won't hurt.

(You'll notice that I cleverly avoided talking about superpolynomial subexponential complexity without explicitly denying its existence. That's because it is a fairly narrow category which serves primarily to distract rather than to inform. If directly asked, you could acknowledge its existence or lie, but don't get side-tracked.)

You can then finish up by explaining that, while the exponential solution is suboptimal, we're still a long way away from P:

Mathematicians and computer scientists have been studying the TSP and other problems like it for some time, and they've found a few tricks to avoid having to try every route. But those techniques still don't scale very well for larger inputs. We would like the "growth factor" to be proportional to a power of the number of cities. Most mathematicians and computer scientists think that's actually impossible, but nobody has managed to prove it yet.

This gives a succinct definition of polynomial growth and an extremely abbreviated statement of $$P \ne NP$$. If you also want to cover the broader notion of NP and NP-complete, that's harder, but doable:

If we want to check whether a given route has at most a given length, that's easy: we just add up the distances along each of the roads. If there is one more city, we have to add one more number, which is pretty fast. But if we want to decide whether there is a route of at most a certain length, that seems to be really difficult. All of the known algorithms scale very poorly for larger inputs, like we saw earlier.

It turns out that there are a lot of problems that are easy to check, but only some of them seem easy to solve. We call these problems $$NP$$, and if they have scalable solutions we also call them $$P$$. Certain problems, like the traveling salesman problem, are very general and powerful, and are called $$NP$$-complete. If you have a scalable solution to one of these special $$NP$$-complete problems, then you can generalize it to every problem in $$NP$$. That would give you a scalable solution to everything in $$NP$$, which would mean that $$P = NP$$. But most mathematicians and computer scientists think that none of the $$NP$$-complete problems have any scalable solutions, so that $$P \ne NP$$.

I've had some success focusing on a single problem that is easy to grasp. Given a carpenter's rule

(Image from here.)
with specific given (integer) lengths for its $n$ ruler sections, and an integer $L$, can it be folded so that its total length is $\le L$?

This is NP-complete by reduction from number partitioning. The reduction is not difficult. Playing around with example rulers quickly leads to the intuition that one must try all possible folding sequences, which is easily felt to be exponential, as the only choice at each joint is: either leave two adjacent ruler sections open end-to-end at $0^\circ$, or folded at $180^\circ$.

For example, these might be the lengths of the ruler sections: $$\{84, 42, 4, 5, 2, 5, 6, 6, 8, 3, 1, 2, 42, 84\} ,$$ and the challenge is to decide if the ruler can be folded into a length of at most $84$. It can be if and only if $$\{4, 5, 2, 5, 6, 6, 8, 3, 1, 2\}$$ can be partitioned into two subsets that sum to $21$ each.

In comparison, computing the length of a given ruler when every joint is folded $180^\circ$ is a linear-time calculation.

This is discussed in Geometric Folding Algorithms Section 2.2.2, but there are many other sources.