World's most popular travel blog for travel bloggers.

Complexity of special instance of Knapsack

, ,
Problem Detail:

Given: primes $p_1,\dots,p_k$, and positive integers $e_1,\dots,e_k$, and a positive integer $M$
Find: integers $d_1,\dots,d_k$ that maximize $\prod_i p_i^{d_i}$, subject to the requirements that $0 \le d_i \le e_i$ and $\prod_i p_i^{d_i} \le M$.

What is the complexity of this problem? Is it NP-hard?

This problem is equivalent to the following:

Given: primes $p_1,\dots,p_k$, and positive integers $e_1,\dots,e_k$, and a positive integer $M$
Find: integers $d_1,\dots,d_k$ that maximize $\sum_i d_i \log p_i$, subject to $0 \le d_i \le e_i$ and $\sum_i d_i \log p_i \le \log M$.

This can be seen to be an instance of bounded knapsack with $k$ items, where the $i$th item has weight $\log p_i$ and value $\log p_i$ and can be used at most $e_i$ times, and where the capacity of the knapsack is $\log M$. (See the footnote below for a more careful statement.) Thus, my problem is a special case of bounded knapsack. It follows that my problem is in NP.

But is my problem NP-hard?

For instance, is there a way to reduce from bounded knapsack to my problem? It's not clear, because my problem limits the weights and values to be something specific related to the log of primes, rather than arbitrary values.

Footnote: strictly speaking, the bounded knapsack requires item weights and values to be integers, whereas $\log p_i$ isn't an integer. However, we can fix this up by picking a sufficiently large constant $K$ and using $\lfloor K \log p_i \rfloor$ as the weight and value of the $i$th item, and use $\lfloor K \log M \rfloor$ as the capacity of the knapsack. With this fix-up, my problem now becomes a special case of bounded knapsack, or reduces to bounded knapsack.

Your problem is at least as hard as the known-prime-factor version of this problem. Shor's reduction also applies to that version, and can be made effective by using this answer rather than the Wikipedia link in Shor's answer.