[Generalization Vs. Reduction]

[Alex Wu]

I am not clear on the difference between proof by Reduction and by
Generalization. What's a clear definition of generalization? Also If
problem A reduces to problem B, is B the generalization of A?

Thank you

[Steven Houston]

It's best not to equate generalizations with reductions.
Generalizations are a special form of reductions, applying only in some
instances.

Problem A is a generalization of Problem B if every instance of B is
also an instance of A. This implies B can be reduced to A.

In general, however, if you can reduce C to D, it's best not to think of
D as a generalization of C (although in some sense a reduction from C to
D implies D is AT LEAST as "general" as C). Since all NP-complete
problems reduce to one another, this would lead to the logic that 3SAT
is a generalization of Vertex Cover, and Vertex Cover is a
generalization of 3SAT, which doesn't make much sense.

Steven