I was asked a question in my algorithms exam which had this as the core question after simplifying. I had written that it would be NP-Hard but I got it wrong my professor is saying that it would be NP-Complete.
Kindly help me resolve my doubt.
2
-
$\begingroup$ By reducing an NP-hard problem to any problem in NP, you show that the problem is in NP. It follows that it is complete for NP. $\endgroup$– John K.Commented Nov 4, 2021 at 10:35
-
$\begingroup$ Thanks for you answer could you please check a question which I had posted with full context. The link is below: [cs.stackexchange.com/questions/145398/… $\endgroup$– GauravCommented Nov 4, 2021 at 12:11
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
A problem that is both NP hard and in NP is NP-complete.
On the other hand, after reading your question I'm not sure what you are asking.
-
$\begingroup$ I have posted a question with full context. Please check it once in the link below: cs.stackexchange.com/questions/145398/… $\endgroup$– GauravCommented Nov 4, 2021 at 12:09