1
$\begingroup$

To show that problem is NP-hard, we take a known NP-hard problem and reduce it to the problem whose NP-hardness we want to prove.

The reduction we need is polynomial time reduction.

But If I take known NP-hard problem and reduce it to some unknown problem by Turing reduction then what I can say about the unknown problem?

I am sure that I can't say it is NP-hard, as the reduction is Turing.

$\endgroup$
2
  • $\begingroup$ @Yuval Filmus I did not understand completely. If unknown problem is also NP then Can I say that in my case unknown problem will be NP-hard? $\endgroup$
    – user94342
    Feb 10, 2019 at 15:49
  • $\begingroup$ See my answer there. There are several other question on the same topic on the site which you might find useful. You can google them. $\endgroup$
    – Yuval Filmus
    Feb 10, 2019 at 15:51

0

Reset to default