# Distributions of input in knapsack problem & related

Let's say that I magicked up some algorithm that would solve subset sum problem in polynomial time, if and only if the input set N was roughly uniformly distributed. Would that count as a polynomial solution, in the general case? Or does a general-case solution have to deal with any distribution?

-

One difficulty is that the reduction of one problem to another usually does not respect the probability distribution. Thus a (worst-case) polynomial-time algorithm for subset sum could be used to provide polynomial-time algorithms for all the other NP problems, e.g. graph colouring, because a graph colouring problem can in principle be transformed into a subset sum problem in such a way that solving that subset sum problem in at most time $T$ would solve the graph colouring problem in at most time $p(T)$ for some polynomial $p$. But an average-case polynomial-time algorithm for subset sum would be unlikely to help much with, say, graph colouring: the subset sum problem you would get from a "typical" graph colouring problem would not be a "typical" subset sum problem.