Teaching NP-completeness - Turing reductions vs Karp reductions

Question

I'm interested in the question of how best to teach NP-completeness to computer science majors. In particular, should we teach it using Karp reductions or using Turing reductions?

I feel that the concepts of NP-completeness and reductions are something that every computer science major ought to learn. However, when teaching NP-completeness, I've noticed that the use of Karp reductions has some downsides.

First of all, Karp reductions seem to be unnecessarily confusing for some students. The intuitive notion of a reduction is "if I have an algorithm to solve problem X, then I can use it to solve problem Y, too". That's very intuitive -- but it maps much better to Turing reductions than to Karp reductions. As a result, I see students who are trying to prove NP-completeness get led astray by their intuition and form an incorrect proof. Trying to teach both kinds of reductions and emphasizing this aspect of Karp reductions sometimes feels a little bit like needless formalism and takes up unnecessary class time and student attention on what feels like an inessential technical detail; it's not self-evident why we use this more restricted notion of reduction.

I do understand the difference between Karp reductions and Turing (Cook) reductions, and how they lead to different notions of NP-completeness. I realize that Karp reductions give us a finer granularity of distinctions between complexity classes. So, for serious study of complexity theory, Karp reductions are obviously the right tool. But for computer science students who are just learning this and are never going to go into complexity theory, I'm uncertain whether this finer distinction is critical is critical for them to be exposed to.

Finally, as a student, I remember feeling puzzled when I ran across a problem like "tautology" -- e.g., given a boolean formula, check whether it is a tautology. What was confusing was that this problem is clearly hard: any polynomial-time algorithm for it would imply that $P=NP$; and solving this problem is obviously as hard as solving the tautology problem. However, even though intuitively tautology is as hard as satisfiability, tautology is not NP-hard. Yes, I understand today why this is the case, but at the time I remember being puzzled by this. (What went through my head once I finally understood was: Why do we draw this distinction between NP-hard and co-NP-hard, anyway? That seems artificial and not very well-motivated by practice. Why do we focus on NP rather than co-NP? They seem equally natural. From a practical perspective, co-NP-hardness seems to have essentially the same practical consequences as NP-hardness, so why do we get all hung up on this distinction? Yes, I know the answers, but as a student, I remember this just made the subject feel more arcane and poorly motivated.)

So, my question is this. When we teach NP-completeness to students, is it better to teach using Karp reductions or Turing reductions? Has anyone tried teaching the concept of NP-completeness using Turing reductions? If so, how did it go? Would there be any non-obvious pitfalls or disadvantages if we taught the concepts using Turing reductions, and skipped the conceptual issues associated with Karp reductions?

---

Related: see here and here, which mentions that the reason why we use Karp reductions in the literature is because it enables us to distinguish between NP-hardness and co-NP-hardness. However, it does not seem to give any answer that's focused on a pedagogical perspective of whether this ability is critical for the learning objectives of an algorithms class that should be taken by every CS major. See also here on cstheory.SE, which has a similar discussion.

Answer 1

I would say very definitely teach using Karp (many-one) reductions. Regardless of the benefits of using poly-time Turing reductions (Cook), Karp reductions are the standard model.

Everybody uses Karp and the main pitfall of teaching Cook is that you'll end up with a whole class of students who become pathologically confused whenever they read a textbook or try to discuss the subject with anyone who wasn't taught by you.

I agree that Cook reductions are in several ways more sensible and that there's no distinction between NP-hardness and coNP-hardness in practical terms, in the sense that they both mean "This problem is pretty hard and you're not going to get a general, efficient, exact algorithm that can cope with large instances." On the other hand, the distinction between NP and coNP isn't entirely an artifact of a theory based on Karp reductions: you don't often talk about graphs that are non-3-colourability or in which every set of $k$ vertices contains at least one edge. Somehow, the "natural" version of the problem often seems to be in NP rather than coNP.

Answer 2

It is better to teach both! A computer science major should know about both of them.

I don't know anyone who uses Cook reductions for teaching NP-completeness, complexity theorists obviously don't, non-complexity theorists typically follow what is the standard definition since Karp's paper and is used in all textbooks (that I know of). It will cause a lot of confusion for them later if you do not follow the standard terminology.

Cook reductions are essentially solving problems using black-box subroutines. They are easy to explain and motivate if your students have some programming experience. They are essential since without Cook reductions you cannot discuss reductions between search problems, optimization problems, etc.

I introduce Karp reduction after Cook reductions and as a special kind of Cook reductions. I think they are essential for the study of $\mathsf{NP}$. This is the distinction between $\mathsf{NP}$ and $\mathsf{P}^{\mathsf{NP}}$. I think it is clear that $\mathsf{NP}$ is much more natural considering its verifier definition.

When we view $\mathsf{NP}$ and $\mathsf{coNP}$ with the goal of finding (deterministic) algorithms to solve them there is not any difference between them. I think this view is the reason you feel Karp reductions are not that important. But that is not the right way to think about $\mathsf{NP}$. The right way to think about $\mathsf{NP}$ is as a very powerful and natural problem specification language. If you take the efficiently verifiable and problem specification language view seriously then you cannot get away with replacing Karp reductions with Cook reductions and $\mathsf{NP}$ with $\mathsf{P}^{\mathsf{NP}}$.

(I also mention Levin reductions in passing, though not always by name, by pointing out that the reduction examples we see throughout the course have this property that given a proof for $x\in A$ we can efficiently compute a proof for $f(x) \in B$.)

Answer 3

The intuitive notion of a reduction is "if I have an algorithm to solve problem X, then I can use it to solve problem Y, too".

an interesting way to approach this particular teaching issue is to realize that NP completeness has similarities and analogies to undecidability which is also unintuitive. students enter class only ever having heard of algorithms that halt. but the principle theorem of TCS is that problems exist for which there is no guaranteed solution, ie the halting problem. and in fact undecidable problems can begin to look far from contrived, and are apparently somewhat ubquitious.

so, the theory is telling us the way to view computation fundamentally as a process that may return an answer under some circumstances. in other circumstances, it may not. for NP completeness and decidability, the fundamental and most general question is, "is there an algorithm that return Y in P time". but this says nothing about an algorithm that returns N in P time. an algorithm could return Y in P time for one instance but not return an answer on other instances. the theory is telling us that there really is a distinct difference here that we have to pay close attention to. if its unintuitive, it means our fundamental intuitions need to be readjusted (as is often the case in theoretical teaching).