4 ms·
> (much like NP-Complete problems are a subset of Complete problems) That sentence is messed up in a bunch of ways. You probably meant: "Turing-undecidable pro
by psykotic 15y ago
> (much like NP-Complete problems are a subset of Complete problems)
That sentence is messed up in a bunch of ways. You probably meant: "Turing-undecidable problems are a subset of NP-hard problems."
- Sniffnoy 15y agoOr 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?)
- psykotic 15y agoI hate it when a pedantic correction backfires. I should have been more careful. :) You're right to raise that question. It's a classical result of computability theory that there exists an undecidable problem that is strictly easier than the halting problem: http://en.wikipedia.org/wiki/Turing_degree#Post.27s_problem_and_the_priority_method http://en.wikipedia.org/wiki/Turing_degree#Post.27s_problem_...
- Sniffnoy 15y agoAlso 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
- JoshuaZ 15y agoUncomputable 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.
- Sniffnoy 15y agoAh, good one. Hooray for padding tricks!
- vbtemp 15y agoHow could undecidable problems possibly be a sub-set of NP-Hard problems? All the complexity classes fall within the realm of computable problems.
- strlen 15y agoNo, NP-hard problems can still be solved, just not in polynomial time.