# 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). 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. 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;}. 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. Dec 10 '17 at 19:32

I have one experience of introducing students with computability and complexity, in one 2-hour lecture. These students are a bit unusual maybe: They are secondary teachers in some scientific field (maths, physics, etc.), most of them quite new to CS and programming. The lecture is part of a larger set of lectures, where they get some intuitions about algorithms and their complexity.

Below is my course outline, which is by no means perfect but may give some ideas. It is very dense for a 2-hour lecture. Many concepts are not formally defined but I rely a lot on their intuition and their (very limited) programming experience.

1. Computability

• What does it mean to compute?
• Many formalizations, that happen to be equivalent
• Choice of Python-like pseudo-code as the model
• Vocabulary: algorithms (=object in the model), partial function, decision problem, computable problem
• Algorithms as data, and existence of a universal algorithm (admitted)
• There exist uncomputable functions, by (un)countability (since some of the students knew the notion)
• The halting problem is undecidable: proved within the Python-like formalism
• Presentation of the Turing Machine model, using mainly examples
2. Complexity

• Complexity of an algorithm versus complexity of a problem
• Idea of grouping problems by difficulty into complexity classes
• Classes P (polytime alg.) and NP (polytime verification alg.)
• Notion of reduction, NP-completeness and Cook-Levin Theorem (admitted)
• P = NP ?
• Yowsers - that really is a lot. Do you have any notion of how much is absorbed/retained?
– Ben I.
May 30 at 20:26
• Not much probably... Yet the goal may differ from other teaching situations. The main goal is that these teachers are exposed to the concepts and to the global picture. Later they may have to introduce at least some of this content to pupils, and they can refer to my lecture notes and other sources I gave to absorb the content they need, digest it before they restore it class. May 31 at 11:10

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 things I have learned as 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 than 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.

Below are links to the two videos that helped me.

Busy beaver is very simple, yet its big-O is higher than 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 me). 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.

• Interesting. Can you please elaborate on "This is clearly not true, for we have done it (here I mean: we = you and I)," pretty please.
– kate
Mar 7 at 16:08
• @Kate will while True: pass halt. Will print ("Hello, world") halt? We can tell if a well writer program can halt. The proof is not saying that we should give up on writing well written programs. It is saying that there are some algorithms that can not be written e.g. one that can tell us for all p(i), where p is a program and i is its input, will p(i) halt. Apr 6 at 22:10