Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
Just a quick "yes" or "no" is all I am looking for :)
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.
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.
