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

Question

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?

Answer 1

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

Answer 2

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 ?

Answer 3

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
• Halting problem

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.