1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

Careful with your terminology there.

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).

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Askeroni Jul 6 '16 at 10:33
  • $\begingroup$ @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. $\endgroup$ – Raphael Jul 6 '16 at 11:53
  • $\begingroup$ 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. $\endgroup$ – Raphael Jul 6 '16 at 11:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.