2
$\begingroup$

The steps to show something is NP-complete is to show it is a member of NP, and then show an NP-complete problem reduces to it in polynomial-time. Why is the first step necessary? Is it possible to reduce an NP-hard problem to an NP-complete problem in polynomial time? Because that would be the only instance in which this is important.

$\endgroup$
6
$\begingroup$

The short answer is that it's because that's the definition of being $\mathsf{NP}$-complete.

Recall that for a problem $\Pi$ to be $\mathsf{NP}$-complete we need the following:

  1. $\Pi \in \mathsf{NP}$.
  2. There exists an $\mathsf{NP}$-hard problem $\Phi$ such that $\Phi \leq^{P}_{m} \Pi$ (where $\leq^{P}_{m}$ is a polynomial time many-one mapping).

What happens then if we leave out condition 1?

In that case "all" we've shown is that $\Pi$ is $\mathsf{NP}$-hard.

Even if we restrict $\Phi$ to being an $\mathsf{NP}$-complete problem, we can still reduce it to problems that are much harder. For example it's trivial to map 3-SAT to QBF-SAT, but QBF-SAT is compete for $\mathsf{PSPACE}$, so definitely not $\mathsf{NP}$-complete unless there's a rather large collapse (at least $\mathsf{NP} = \mathsf{PSPACE}$).

Going further (and thanks to David Richerby for being sensible), there are versions of $\mathsf{NP}$-complete problems that are $\textsf{NEXP}$-complete, for example SUCCINCT 3-SAT is a generalisation of 3-SAT (the reduction from 3-SAT to SUCCINCT 3-SAT is less obvious, but not tricky). However we know unconditionally that $\mathsf{NP}\neq \mathsf{NEXP}$, so SUCCINCT 3-SAT is not in $\mathsf{NP}$.

As you note, it is unlikely that we can reduce, in polynomial time, an $\mathsf{NP}$-hard problem that's unlikely to be in $\mathsf{NP}$ to a problem in $\mathsf{NP}$ (again, it would imply some collapse in complexity classes). Where you went off track is identifying this as the only important case.

$\endgroup$
1
$\begingroup$

By definition a problem is NP-Complete when it is in NP and it is NP-hard. Obviously, you need to proove these two conditions to coincide with the definition.

Why do we have belonging to NP in the definition? By calling a problem NP-Complete we want to show that this problem is the hardest among all NP problems. If you proved only hardness, it could be just a problem from a harder class than NP.

Is it possible to reduce NP-hard problem to NP-complete? This would mean that the NP-complete problem is harder than NP-hard one. Still the question why this NP-hard one is the hardest among all NP problems remains.

$\endgroup$

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.