# algorithms – Reductions versus generalizations

In the questions above, we are saying that a special case of any of the problems above are NP-complete complete. This seems like a misnomer though. Shouldn’t this be a specialization rather than a generalization?

No. The problem you are proving NP-complete is a generalization of a known NP-complete problem. E.g. the MAX-SAT example contains Boolean satisfiability; just set $$g$$ large enough to demand satisfaction of all the clauses.

Another part of my confusion is how these so-called generalizations compare or contrast to reductions. Are we saying that some (special) version of a problem is NP-complete and therefore all the other instances are NP-complete? I thought that we needed to show that all instances of the problem are the NP-complete problem.

No, we’re saying that if an NP-complete problem can be specified using the rules that describe a different problem without changing those rules, then that different problem is NP-hard, and is also NP-complete if that different problem is in NP.

Regarding the direction of reductions: we reduce from a NP-complete problem (the hard problem) to the problem that we have at hand. For example, in the reduction from 3SAT to independent set we reduce from 3SAT that we know is NP-complete to what we have at hand, the independent set – did I misunderstand? Are these reductions generalizations? I thought that they were for all instances of the independent set.

No, you should just think of reductions as reductions. A generalization of an NP-complete problem contains that problem as a special case within the generalized problem. A reduction provides a way to go from an instance of one problem to an instance of another without regard to whether one problem is a special case of another.

Are generalizations reductions?

No, they are an expansion of the original problem that still contains the original problem. E.g. Boolean satisfiability is a generalization of 3-satisfiability because 3SAT is contained within the expanded problem set.