Natural notion for computational hardness

Question

When I teach students concepts like intractable problems and efficient algorithms in discrete structures or data structures and algorithms, it is difficult for students to intuitively grasp somewhat artificial concepts of asymptotic time complexity and polynomial growth rates. Artificial $NP$-complete problems were known before the discovery of Cook's first natural $NP$-complete problem, which sparked huge interest in the field. Under some acceptable definition of natural:

What is the most natural way to express the computational hardness of natural problems to students who encounter the subject for the first time?

EDIT: Motivated by Marc's answer, it would be more natural to find how hard is the self reducibility of clique problem. For instance, How hard is it to reduce an instance of clique of input size $(1+ \epsilon)n$ to an instance of size $n$ using Turing reduction?.

Answer 1

Just what makes growth rates such as O(n²) artificial — just the fact that it isn't one specific monotonic function? Or is it the fact that it's a family of functions in itself, and not just some simple number which comes from something obvious about the problem?

At the very least, your students should be able to grasp the purpose, and in a sense the meaning, of asymptotic notation by observing how the tediousness of performing arithmetic scales with the size of the numbers — that it gets more tedious for larger numbers, and that adding two n-bit numbers is less tediuous than multiplying them. Hopefully they should percieve a difference! If they can, then you have got them where you want them. Point out that the difference is smaller when you have smaller numbers: obviously the difference is one which grows with instance size. Point out to them the nested iterations in the multiplication algorithm. And now you have motivated caring about the difference between O(n²) time and O(n) time. Get them to do matrix computations next to give them a taste of O(n³), and point out the nested iterations there. They should get the idea after that.

I would say that exponential-time versus poly-time often amounts to "searching through a combinatorial explosion versus performing a bounded number of nested iterations", which is about as natural a distinction as possible between approaches to solving problems (e.g. in computer programming). But you cannot motivate complexity of problems of any sort, to people who do not themselves spend time solving problems and so who have no taste for the idea that certain ways of solving things (or solving different kinds of problems) take different amounts of work, and that differences between algorithms come from some place. You can't convince someone of these things unless they can have enough "empathy" for the computer to viscerally feel the extra work that is being done in one algorithm, versus another; to be aware of the layers of computing or of searching which it is doing, to actually hope that the problem has enough structure to narrow the solution space beyond just nested loops. They must be able to appreciate the existentially Sisyphian futility of trying to solve instances of SAT just by looking forlornly for a solution brute-force. This sort of perspective comes from solving problems oneself, and being self-aware of what one is doing; and I think it is perfectly natural to ask how much the tediousness of the task (i.e. how many computations you are doing) scales with the size of the problem.

If your students can't grasp this, tell them that the "difficulty" of adding numbers by high-school techniques is rated as 1; that of multiplying numbers is rated as 2; that sorting an unordered list has a rating between 1 and 1.000001 if you do it in the right way; and that there are no techniques for solving SAT whose rating is less than infinity; and move on from there — because you're not likely to do much better than this pedagogically without inventing a novel complexity measure, or obtaining more engaged students.

Answer 2

I find that the most "natural" way to get an intuition of complexity classes is to revert to Turing's starting point and try to solve the problem "manually".

Start with a sorting task. From a jumble of, say, five words have the class order them alphabetically. This should be easy. Then double the number of words, and repeat the exercise. It will be obvious that, though the second problem is harder, it isn't that much harder.

Next try a traveling salesman task. Start with a grid of say three cities with distances between them. The class will probably be able to solve this in short order. Now double the number of cities to six, and continue with the exercise until everyone's head is spinning.

An experience like this is very likely to leave a lasting visceral impression that a purely technical introduction may not.

Answer 3

Use some slides and start with subset-sum:

Show them a balance with a 100Kg weight on a plate. On the side of the balance put 5 small weights and ask if some of the weights are enough to overbalance the 100Kg weight.

Then ask if some of the weights can be used to exactly balance the 100Kg weight, i.e. their sum is exactly 100Kg (suppose 3 of them is a solution).

Then repeat the game with 10 small weights (and a harder solution that involves 6 of them).

Then repeat the game with 15 small weights (and a harder solution that involves 6 of them).

If they do not solve it in a minute highlight those who form a solution and ask to them to verify that their sum is exactly 100Kg (and they will do it in a few seconds).

In my opinion a very natural way to mark the difference between easy (> 100Kg?) and hard (= 100Kg?) and the difference between finding and verifying.

... and after the first lesson if you want to totally confuse them show a shuffled Rubik's cube and say "Every shuffled Rubik's cube can be solved in less than 21 moves!". This marks the difference between problems that are hard and problems that are supposed to be hard only because we don't know "how to do it". :-D :-D :-D

Answer 4

I honestly think there is no "natural" notion for computiational hardness; it is inherently a creature of human minds.

Maybe a simple analogon can help to understand polynomial growth. Give your students (virtually) the following task: With a sensor that can scan one cubic centimetre, find a cent piece. How long does it take you if you have to search

• along a line of length 1m (10m, 100m, 1km)?
• in an area of 1m² (100m², 10,000m², 1km²)?
• in a tank of water that takes 1m³ (1000m³, 1e6m³, 1km³)?

This reduces computational complexity to measures known from elementary school; who has not wondered then why 1000m give 1km, but 1000m² do not give 1km²?

Exponential growth can best be explained by brute force: we start with a single bacterium. This kind separates every six hours and never dies. Make a table or better, pictures: After one day, there are 16 bacteria. After two days, 256. And so on. After 18 days, our colony weighs ten million tons. That should make an impression. You can make it a search problem again: assume our start bacterium had a marble in its body that is passed along to one offspring. After 20 days, how long do you have to search for the marble if you can only examine one (or ten, hundred...) bacteria at a time?

Another thing often used in magazines for children is folding a piece of paper: how often do you have to fold to reach the moon? (not too often) Also popular: the guy with 1, 2, 4, ... grains of rice on the chess board. Creating a full table of a binary function with 3, 4, ... parameters is telling, too.