Search code examples
computer-sciencetheorycomputation-theory

what is the Non-cyclical definition of NP-hard?

I am trying to comprehend the concepts NP, NP complete and NP hard according to Wikipedia.

If I inderstand the given text correctly:

EDIT: corrected according to David

NP == decision problem whose answer can be verified in polynomial time (given the solution)

NP complete == NP and NP hard simultaneously

NP hard == there is a NP complete problem which is polynomial time Turing reducible to it.

So in order to understand the concept of NP completeness, I need to understand the NP hardness first. So I try to analyze what is NP hard according to the above statements. So I get:

NP hard == there is a problem which is NP hard and NP simultaneously, which is reducible to it. But there is a cycle in the definition. What is the noncyclical definition?

Solution

  • You can also define NP-complete as a problem such that any NP-problem can be reduced to it in polynomial time. That definition should remove your cycle.

    Your definition of NP-hard seems backwards. It should be that a problem is NP hard if some NP-complete problem (thus any NP problem) can be reduced to it in polynomial time.

    You can see more detail here: http://en.wikipedia.org/wiki/P_versus_NP_problem