0
$\begingroup$

Are all np-complete problems also np-hard?

In other words, is np-complete a subset of np-hard?

I don't think it is entirely clear from the illsutration below, so I just wanted to quickly ask to ask to be completely sure. The np-hard area also includes the np-complete section right?

enter image description here

Just a quick "yes" or "no" is all I am looking for :)

$\endgroup$

2 Answers 2

1
$\begingroup$

A problem is said to be NP-complete if it is in both NP and NP-hard, so yes all NP-complete problems are also NP-hard.

$\endgroup$
-1
$\begingroup$

No (unless you find a proof for it that will make you world famous as a mathematician and computer scientist). NP-complete problems are in NP and can be used to solve any problem in NP. NP-hard problems can be used to solve any problem in NP but need not be in NP.

NP-complete equals NP-hard plus NP.

$\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.