In a previous post, I discussed one of my favorite proofs from the Theoretical Computer Science question-and-answer site. Today, I’d like to present another short-but-awesome piece from the same site.
Adam Crume asked:
If a problem is NP-hard (using polynomial time reductions), does that imply that it is P-hard (using log space or NC reductions)? It seems intuitive that if it is as hard as any problem in NP that it should be as hard as any problem in P, but I don’t see how to chain the reductions and get a log space (or NC) reduction.
I didn’t really think much about this question — or much of it, to be brutally honest — and a couple commenters didn’t either. Crume basically got criticized for mixing apples and oranges, asking an ill-formed question because he combined two different notions of reduction in the same sentence. Fortunately, Noam Nisan answered with the following three-sentence gem:
No such implication is known. In particular it may be that in which case all problems (including trivial ones) are NP-hard under poly-time reductions (as the reduction can just solve the problem), but trivial ones (in particular ones that lie in L) are surely not P-hard under logspace reductions (as otherwise L=P). The same goes for NC instead of L.
I learned a lot from that answer, and I bet others did too, given how dismissive we were of the question. This reminded me of perhaps my favorite research advice: don’t be afraid to ask dumb questions (and answer them).
Adam Crume’s original question is here.