0
$\begingroup$

Maybe this is quite simple, but I am having some trouble how to do this reduction. I want to reduce Subset Sum to Almost Subset Sum.

Subset Sum: given a set of positive integers $A=\{a_1,a_2, \dots,a_n\}$ and an integer $M$, decide if there is a subset of $A$ with a sum equal to $M$.

Almost Subset Sum:

Input: a set of positive integers $A=\{a_1,a_2, \dots,a_n\}$, and a positive integer $M$.

Goal: decide whether there is a subset of $A$ with sum $S$ such that $|M −S| < d$ where $d = ⌊\log M ⌋$?

$\endgroup$
  • 1
    $\begingroup$ cs.stackexchange.com/q/11209/755, cs.stackexchange.com/q/1240/755 $\endgroup$ – D.W. Apr 21 at 19:27
  • 1
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Apr 21 at 19:28
  • 1
    $\begingroup$ Try multiplying everything ($A$ and $M$) by a large enough number. $\endgroup$ – Yuval Filmus Apr 22 at 2:47
  • $\begingroup$ Thank you both for your input! I tried many different approaches (adding, logging, dividing, and even multiplication). I thought I had forgot about a trivial logarithmic rule. I read a bit and tried your approach Yuval. Multiplying A and M by 10 seems to have done it! $\endgroup$ – red31 Apr 22 at 12:38

Your Answer

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

Browse other questions tagged or ask your own question.