# How do I construct a basic lesson on computational complexity and undecidability?

Essential Understanding 4.2 of the AP CS Principles curriculum is as follows: "Algorithms can solve many, but not all, computational problems." Among the topics I am expected to cover in the context of this standard are algorithms that run in a reasonable time v. those that don't, the difference between solvable and unsolvable problems, the use of a heuristic, and the existence of undecidable problems.

My plan is to cover the 0/1 knapsack problem, the heuristic of a greedy algorithm, and the halting problem. This is a relatively small part of the course and is assessed by only a couple of multiple-choice questions on the AP Exam, so I don't need more than one lesson (or two) of material.

That said, I am afraid any one-day lesson will be inevitably reductive as these are complex topics. Moreover, the students are new to programming and computer science in general, so I need to balance abstract with theory with concrete, relevant examples.

What lesson ideas, examples, and/or analogies do well to serve the teaching of this standard?

• What does the knapsack problem have to do with undecidability? A high computational complexity is radically different from undecidability. I fear that by teaching them together, you're going to confuse the students into thinking that exponential-worst-case problems are unsolvable, even though they get solved daily (e.g. in compilers). – Gilles Nov 20 '17 at 0:19
• I edited my question title. In the context of the curriculum, the topics of complexity and undecidability go together standards-wise. They are sub-categories of the EU quoted above. Given their importance relative to other topics and the limitations of time, I’d like to transition from complexity to undecidability in the context of a single lesson if possible. – Peter Nov 20 '17 at 0:41

The hard parts of this are hard for everyone, of course: P = NP (or not). But the others aren't too difficult to get across in a short period of time, especially if the students have something of a math background.

You can easily construct problems that grow exponentially and whose programs for solution must also grow at that rate. Drawing a completely connected graph for example and adding vertices.. Listing all of the permutations of n distinct elements, for example.

The halting problem is great, of course, and you can often use a graphic to illustrate the problems: a machine that takes machines as one input and tapes as another. But you can also convince students that most problems don't have solutions as there are only a countable number of computer programs given any finite character set. But the number of problems is uncountable. The fact that we know of only a few unsolvable problems is similar to the fact that we know only a few non-algebraic numbers, though most (again uncountably many) real numbers are not algebraic while only countably many are algebraic.

But laying out the broad outlines (feasible, non-feasible, non-computational) lets you say a few words about what we don't yet know and why CS, like math, isn't a fixed body of knowledge, but a field ripe for research.

You can even go a bit farther and talk about the issue that for some problems a solution is hard to find, but easy to check, which is fundamental to encryption. It is hard to find factors, but easy to check that they are factors once found. This gives you a way to talk about nondeterministic algorithms of which "repeatedly guess and check" is one variety.

One final idea that can be fun. Assuming you have already covered sorting to some extent, you can have the class, or small groups within the class, brainstorm the most inefficient sorting algorithm they can think of. But it needs to be an algorithm, not just randomness. But "Mix the values and check if sorted. Repeat until done." is actually an algorithm if your mixer is truly random. That is, it is guaranteed to sort.

If your students know some calculus, you can mention Newton's Method for finding zeros of a function. While it seldom gives you the exact value it is a process (pseudo algorithm) for guessing and then improving the guess in the next iteration. I say "pseudo algorithm" since it isn't guaranteed to terminate or to find an exact answer. But it is an improvement on pure "guess and check"

A resource on Non Computability and its relation to self reference and recursion is this paper by Owen Astrachan of Duke

• Be careful with naming things: In english “halt” is a verb. If you say halt, you are giving an order. To discover if someone can halt, you would ask “Can you halt?”. In OO programming we could write if ( program(s).withInput(s).willHalt() ) {loopForever()}else{return true;}. – ctrl-alt-delor Nov 20 '17 at 14:20
• Drawing a completely connected graph for example and adding vertices. — I think you need a better example. The time to add a vertex and all its incident edges to a complete graph grows linearly with the number of vertices, not exponentially. Drawing a complete graph takes time quadratic in the number of vertices, assuming each edge can be drawn in constant time. Even if the time to draw an edge scales linearly with its length, and the vertices are evenly spaced on a circle whose radius is proportional to the number of vertices, drawing a complete graph takes "only" O(n^3) time. – JeffE Dec 10 '17 at 19:32

I was a software engineer (not a computer scientist), I have self taught CS, some of it recently. I now teach computing.

One of the think I have learn at a teacher, is not all knowledge should come from the teacher. It is better to get the students to do some activity, to actively learn.

A few years ago I saw two videos, one on the halting problem. One on NP, it was the busy beaver problem. The first $O(x) > O(n!)$, that I had seen.

Therefore get the students to watch the videos for homework, then to solve Busy beaver for n<=4, and spend an hour on n=4 (I think it is 4 that can be done in less that an hour. And 5 would take years on the fastest computer. But you should check.) In class discuss the findings, and then get them to act out the parts of the machine in the halting proof. Then discuss that.

Bellow are links to the two videos that helped me.

Busy beaver is very simple, yet its big-O is higher that super-exponentiation.

Note: Be careful with the halting problem. I keep hearing it said that it is impossible to determine if a program halts. This is clearly not true, for we have done it (here I mean: we = you and I). It should be stated that “it is impossible to determine, in the general case, if a program halts.” That is it is impossible to make a program/machine that will be able to tell you if a program/machine halts, that will work for all program/machine inputs.