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$.
