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.

  • $\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$
    – Pål GD
    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$
    – Gaurav
    Nov 4, 2021 at 12:11

1 Answer 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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