Cheap and Secure Web Hosting Provider : See Now

Complexity of special instance of Knapsack

, , No Comments
Problem Detail: 

Consider the following algorithmic task:

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.

Asked By : D.W.
Answered By : Ricky Demer

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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback