Ah, thanks for the correction. I always thought of complexity as being a subset of computability theory (much like NP-Complete problems are a subset of Complete problems), but you are right-- they're separate disciplines.
Will need to read this, of course. My fault for replying before at least attempt to scan over the full essay linked from the post.
Or perhaps he meant that NP-complete problems are a subset of NP-hard problems? But that wouldn't be analogous...
(Actually, are uncomputable problems necessarily NP-hard? This sounds obvious at first, but then you realize, wait, why would the reduction be polynomial time? If we assume our undecidable problem is at least as hard as the halting problem there's an obvious constant-time reduction, but what if it's intermediate? Is this something that's known?)
Uncomputable problems are not necessarily NP-hard. You can for example encode a version of the halting problem such that the instances are simply very long. For example, consider the language L defined by k is in L iff k=2^2^2^n for some n and nth Turing machine halts on the blank tape (some reasonable listing of Turing machines). In order to feed an NP-hard problem to an L-oracle, one needs to ridiculously expand the length of the problem far more than polynomial length so this certainly can't be done in polynomial time.
Also I just realized that just because something is at least as hard as the halting problem, doesn't necessarily mean it stays so when you restrict to polynomial-time reductions. So maybe even what I stated above isn't true. :-/ Well, the halting problem is NP-hard, at any rate. :P
> I always thought of complexity as being a subset of computability theory
But while that's certainly true in a sense, that doesn't imply what you stated -- just because they care about computability theory doesn't mean they care about this aspect of it.
Will need to read this, of course. My fault for replying before at least attempt to scan over the full essay linked from the post.