To show the NP-hardness of a problem, one need to choose a known NP-hard problem and find a polynomial reduction from the known problem to his problem in hand. Theoretically, any NP-hard problem can be used for the reduction, but in practice, some of the problems are more easily reduced than others.For instance, 3-SAT is usually a better choice for constructing a reduction than SAT because the former one is more restricted than the latter one, 3-partition is usually an easier choice than bin packing, ...One way to find such good problems for the reduction is to do a statistical analysis over the existing reductions. E.g., one can shape all the pairs of from -> to reductions of the book Computers and Intractability: A Guide to the Theory of NP-Completeness(or other resources)and draw a histogram of the problems in the from set.Then we can find out which problems are more commonly used for reductions.I wonder if such a statistical analysis makes sense at all. Has such a research been already conducted or not? If not, what is your guess about the most commonly used problems for reductions.The reason I am asking this question is that I have already done a few proofs of NP-hardness, but almost all of them rely on reduction from the same problem (3-partition). I am looking for other options to use in my proofs.
NP-hardness proof: looking for some good restricted np-hard problems
np hardness;reductions