# Is the prime factorization problem not an instance of the change making problem?

When using as the set of coins all logarithms of the prime numbers or numbers in general, and when using the logarithm of the number to be factored. The problem is just finding the logarithms that can be used to make the total. But then the change making problem is listed as non NP problem, but the prime factorization problem is found to be NP complete. Can anyone explain why this is?

When using as the set of coins all logarithms of the prime numbers or numbers in general

The change-making typically assumes a finite set of coins.

You can, of course, extend it to infinite sets of coins but then you get a different problem. Depending on the exact formulation, it seems plausible that integer factorization would reduce to that new problem.

But then the change making problem is listed as non NP problem, but the prime factorization problem is found to be NP complete.

The general change-making problem is certainly in NP since it can be solved by integer programming. I do not know if it is NP-hard, but the common algorithms do not show that it is in P since they are only pseudo-polynomial. This shows, at least, that the problem is not strongly NP-hard.

Real-world change-making usually deals with canonical sets of coins for which a simple greedy algorithm works; it runs in constant time assuming a constant set of coins and the uniform cost model.

Integer factoring, on the other hand, is not known to be in P nor NP-hard; it's an open problem, and if P ≠ NP it may be in neither (but in NPI instead).

• Wait, is it not a subset sum problem anyways, why is it not in np when the knapsack problem is? And the amount of primes in the set is always lower than the number so it is not infinite. Jul 6 '16 at 10:33
• @Askeroni 1) Please visit this link I posted. You are confused about what "NP" means. 2) As I clearly wrote, change-making is in NP. 3) The input number is unbounded, so we'll also need an unbounded number of primes. A finite number for each instance, true, but all primes for the whole problem. 4) This classification of "subset sum problems" is not helpful for determining complexity; all NP-complete problems have easy derivates.
– Raphael
Jul 6 '16 at 11:53
• In summary, your issues are with basic notions of complexity theory. Take a step back and revisit them. Our reference material can be of help.
– Raphael
Jul 6 '16 at 11:54