NP-Complete proof by "reverse" reduction?

Question

I have been studying a collection of networking problems for my thesis and have proven quite a few of them to be NP-Complete via Karp reduction. The thing is, I'm so tired of doing the whole proof over and over and it's getting redundant in my write-up. I'm hoping to take a shortcut by showing that my new problems are superproblems of NP-Complete ones and using that info to do a much shorter proof that they are also NP-Complete. I haven't been able to find any resources online to know if this is trivial, or if I have to do the full fledged Karp reduction.

For example, everyone uses the fact that SAT is NP-Complete in order to prove that 3-SAT is NP-Complete. We know 3-SAT is a subproblem of SAT and that SAT is NP-Complete. So we reduce SAT to 3-SAT, and Bob's your uncle. However, what happens if we know 3-SAT is a subproblem of SAT and this time someone tells us that 3-SAT has been proven to be NP-Complete. They then task us with proving that SAT is also NP-Complete. Would I need to reduce 3-SAT to SAT, or is the fact that SAT has a known NP-Complete subproblem sufficient evidence to conclude that SAT is also NP-Complete?

In other words, can I draw the conclusion that if Problem A is NP-Complete and also a subproblem of Problem B, then B is automatically NP-Complete? Is it always true that any problem is at least as hard as its hardest subproblem?

Answer 1

3-SAT is easily reduced to SAT, by using the identity function. This shows that SAT is NP-hard, knowing already that 3-SAT is. To know that SAT is NP-complete we also need to show that SAT is in NP, which is not difficult.

This holds more generally. Suppose $A$ is a subproblem of $B$. By this I mean that each instance of $A$ is also an instance of $B$. Then $A$ can be reduced to $B$ by mapping each instance of $A$ to itself. The conclusion is that if $A$ is NP-complete and $B$ is in NP, then $B$ is also NP-complete. Often, showing that $B$ is in NP is straightforward, so your idea is a good one.

Answer 2

As long as every instance of the known NP-complete subproblem is an instance of the problem B then problem B can't be any easier than NP-complete. Problem B can be harder than NP-complete problems however, so if you need the specific result of NP-completeness rather than something higher in the polynomial hierarchy, then you still need to do the Karp reduction.

Answer 3

If we think of decision problems as languages over some fixed alphabet $\Sigma$ and the subproblem relation as inclusion, we see that the answer must be no. We cannot conclude that if $L_1 \subseteq L_2$ and $L_2$ is NP-complete, then so is $L_2$. For we can take $L_2$ to be the total language $\Sigma^*$, which is trivially decidable in constant time.

If we instead use the notion of poly-time reducibility, the answer is yes; this follows from the transitivity of poly-time reducibility.