Trivial reduction question is deep

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 L \neq P=NP 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.


3 responses to “Trivial reduction question is deep

  1. In the spirit of asking dumb questions:

    Does the search for a Unified Field Theory intersect with any known problem in Computational Complexity?

  2. Thanks for the pointers, Aaron.
    I think there is one school of thought in Theoretical Physics where they attempt to use mathematical symmetries to predict the existence of unknown particles.
    Check out “E8” and “surfer dude stuns physicists with Theory of Everything.”
    (One day I will figure out how to cut and paste web addresses.)

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s