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.
In the spirit of asking dumb questions:
Does the search for a Unified Field Theory intersect with any known problem in Computational Complexity?
Hi, Jim Blair! I think the verdict is out on your question, though in one sense physical reality has nothing to do with, e.g., whether P=NP, as the P=NP problem is a “purely mathematical” statement about the behavior of Turing machines. That said, you might be interested in Scott Aaronson’s Computational Intractability As A Law of Physics, this TCS.SE question-and-answer that discusses (and partially rebuts) Aaronson’s position, and Seth Lloyd’s essay about the absolute physical limits of computation.
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.)