Skip to main content

Return to Question

Title correction - NP must be all captialised
Link
edit approved Dec 19, 2014 at 8:13
chiwangc
edit approved Dec 19, 2014 at 8:13
chiwangc
  • 3.6k
  • 16
  • 28
  • 32

Np NP-Complete VS NP-Hard

Formatting + tags
Source Link
Bernhard Barker
Bernhard Barker
  • 55.7k
  • 14
  • 111
  • 143

I am trying to understand the difference between NP-Complete and NP-Hard.

Below is my understanding

NP-Hard problem is one that is not solvable in polynomial time but can be verified in polynomial time. NP-Complete is one that is in NP and is also NP-Hard.

An NP-Hard problem is one that is not solvable in polynomial time but can be verified in polynomial time.
An NP-Complete problem is one that is in NP and is also NP-Hard.

Is the above definition correct? If so, What about problems not In NP but NP-Hard. Wouldn't they be harder than NP-Complete problem, say they can only be solved and verified in exponential time?

I am trying to understand the difference between NP-Complete and NP-Hard.

Below is my understanding

NP-Hard problem is one that is not solvable in polynomial time but can be verified in polynomial time. NP-Complete is one that is in NP and is also NP-Hard.

Is the above definition correct? If so, What about problems not In NP but NP-Hard. Wouldn't they be harder than NP-Complete problem, say they can only be solved and verified in exponential time?

I am trying to understand the difference between NP-Complete and NP-Hard.

Below is my understanding

An NP-Hard problem is one that is not solvable in polynomial time but can be verified in polynomial time.
An NP-Complete problem is one that is in NP and is also NP-Hard.

Is the above definition correct? If so, What about problems not In NP but NP-Hard. Wouldn't they be harder than NP-Complete problem, say they can only be solved and verified in exponential time?

Source Link
ade19
ade19
  • 1.2k
  • 5
  • 15
  • 29

Np-Complete VS NP-Hard

I am trying to understand the difference between NP-Complete and NP-Hard.

Below is my understanding

NP-Hard problem is one that is not solvable in polynomial time but can be verified in polynomial time. NP-Complete is one that is in NP and is also NP-Hard.

Is the above definition correct? If so, What about problems not In NP but NP-Hard. Wouldn't they be harder than NP-Complete problem, say they can only be solved and verified in exponential time?