1
$\begingroup$

i want to do a polynomial reduction from the Independent-Set-Problem which is NP-complete to the AUCTION-Problem, to show that AUCTION $\in$ NP-complete, but why do i always have to show first, that our problem(in this case AUCTION) $ \in $ NP?

$\endgroup$
3
$\begingroup$

Because a problem L is NP-complete if and only if:

  • L is in NP
  • L is NP-hard: every problem A in NP can be polynomially reduced to L.

So to show that L is NP-complete, you have to demonstrate both the properties.

$\endgroup$
  • $\begingroup$ Is is not right to say, if i successfully reduce a NP-complete problem L to another problem K, K has the properties of an NP-complete problem, which implicates that K is in NP and K is NP-hard? $\endgroup$ – M.Mac Feb 6 '17 at 14:59
  • 1
    $\begingroup$ @M.Mac This is my idea: think about unSAT; the problem is in coNP, since SAT is in NP. We can define a nondeterministic Turing Machine that solves unSAT in polynomial time, since we have a machine with the same properties that decides the complementary problem. But a problem is in NP if it has a polynomial verifier, and we don't know one for unSAT yet. In the same way, your reduction shows that K is NP-hard and that there is a NTM that solves K in polynomial time, but does K have a polynomial verifier? $\endgroup$ – Ack. Feb 6 '17 at 15:34
  • 1
    $\begingroup$ @M.Mac No. By successfully reducing an NP-complete problem $L$ to another problem $K$, you've proved that $K$ is NP-hard. NP-complete means NP-hard and in NP. In particular, the halting problem is NP-hard but it certainly isn't in NP, so it's not NP-complete. $\endgroup$ – David Richerby Feb 6 '17 at 15:55
  • $\begingroup$ @DavidRicherby I see, but is NP-hard not defined as, all problems L $\in $ NP which are succesfully reduced to another problem K? Why does it not implicate that K is in NP? $\endgroup$ – M.Mac Feb 6 '17 at 18:27
  • 1
    $\begingroup$ @M.Mac No, that's not how NP-hard is defined. You can look that up anywhere. $\endgroup$ – David Richerby Feb 6 '17 at 18:53

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.