I’m teaching complexity theory this fall. (Check out my syllabus and lecture notes!) I’ve fallen about half a lecture behind where I thought I would be at this point, so to catch up I’m debating whether to omit Ladner’s theorem. Should I? Here are the main reasons I was originally planning to cover it:
- It is a famous result.
- The proof is not very difficult (so it doesn’t take a lot of time to cover); though see below.
- It is in Chapter 3 of the Arora-Barak book, which I am roughly following.
On the other hand, once I thought about omitting it, I came up with stronger reasons not to cover it:
- To me it seems like a “so what?” result. So there are languages in NP\P that are not NP-complete…who cares? (It is a natural question, but the result isn’t very satisfying because you get a completely ridiculous language.) I am also unaware of any interesting results that are proved by relying on Ladner’s theorem.
- I find the proof extremely technical, messy, and un-illuminating.
- I am not aware of the specific techniques being useful in some other context, certainly not for anything I was planning to teach later on this semester.
It is worth comparing Ladner’s theorem to the two other results in Chapter 3 of Arora-Barak (that I will cover this semester): hierarchy theorems, and the [BGS] result that the P vs. NP question does not relativize. Point-by-point:
- I think both these results are very important in their own right. Moreover, hierarchy theorems are invoked frequently in proofs of other results. The [BGS] result is interesting as an illustration of being able to rule out a particular approach to solving a problem.
- The proofs of both these results are somewhat technical, but I find them much cleaner than the proof of Ladner’s theorem. I think they also both have a pretty clear high-level intuition (something I find lacking in the proof of Ladner’s theorem).
- The techniques used are applicable elsewhere (though not anywhere later in my class). The hierarchy theorems offer a clear demonstration of diagonalization (and, of course, are useful starting points when trying to prove other hierarchy theorems). Oracle separations were in vogue a decade or two ago in complexity, and are still popular (though in a different sense) in cryptography. I could imagine that when starting to work on many complexity questions, even today, a first question would be to ask whether the statement you are trying to prove relativizes.
I guess I’ve managed to convince myself not to cover it this semester. Anyone want to try to convince me otherwise?