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.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
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:
- $\Pi \in \mathsf{NP}$.
- 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.
answered Nov 30, 2016 at 1:09
$\begingroup$
$\endgroup$
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.
