2
$\begingroup$

According to this source,

If A is reduced to B and A ∈ class X, then B cannot be easier than X. This reduction is used to show if a problem belongs to NPH – just reduce some known NPH problem to the given problem. This reduction thus gives a lower bound for the complexity of B.

Now consider the following scenario: X is an NP-hard problem. It is polynomial-time many-one reducible to problem Y. This makes Y NP-hard. My question is, it could be possible that X has a better solution like NP or P, which we could not find. Then why should Y be NP-hard? It could be NP or P. If Y turns out to be P (assume) then X becomes P.

$\endgroup$
0

1 Answer 1

4
$\begingroup$

All NP-complete problems are "equally hard", in the sense that if one of them is in P, then all of them are in P. Similarly, if one NP-complete problem can be solved in quasipolynomial time (that is, time $e^{O(\log^C n)}$ for some constant $C$) then all of them can be solved in quasipolynomial time.

Some NP-hard problems are harder than others, but all of them are at least as hard as all NP-complete problem. That is, if some NP-hard problem is in P, then all NP-complete problems are in P. Similarly, if some NP-hard problem can be solved in quasipolynomial time, then the same holds for all NP-complete problems.

However, some NP-hard problems are provably harder than others. For example, the halting problem is NP-hard, but in contrast to all NP-complete problems, it cannot be solved in exponential time; in fact, it cannot be decided at all!


My question is, it could be possible that X has a better solution like NP or P, which we could not find.

There are two problems with this statement. The first is the assumption that NP is a better complexity class than NP-hard. In fact, all NP-complete problems are both NP-hard and in NP (that's the definition of NP-completeness), so it's in fact common for problems to be both. NP-hardness is a lower bound on complexity, whereas being in NP is an upper bound. The two are not contradictory in any way.

The second problem is the assumption that it could be possible that X is in P. As explained above, that would imply that P=NP, which most people consider unlikely. An NP-hard problem cannot be "easy" – it's at least as hard as any problem in NP, and in particular at least as hard an any NP-complete problem.


Then why should Y be NP-hard?

You can prove that Y is NP-hard if you can reduce, in polynomial time, another NP-hard problem X to it. I won't repeat the proof here, since it can be found in textbooks, lecture notes, and even here on Computer Science.


If Y turns out to be P (assume) then X becomes P.

That's correct, but there is no contradiction here. This is actually the point of NP-hardness. We don't believe that Y is in P, since that would imply that X, as well as many other problems, are also in P.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.