Teaching NP-completeness - Turing reductions vs Karp reductions 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.
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$&nbsp;vertices contains at least one edge. Somehow, the "natural" version of the problem often seems to be in NP rather than coNP.