# SUBSET SUM "with error"

Has a SUBSET-SUM "with error" variant been studied - and with error, I mean, instead of a single target value $$k$$, a target interval $$[k-\varepsilon,k+\varepsilon]$$ ($$\varepsilon>0$$ very small)? EDIT: In this variant, the input is positive real numbers rather than integers.

if so....

1. Is this weaker variant still NP-Hard?
2. Suppose we turn this variant into a search promise problem; we're guaranteed the input multiset has a subset whose sum is in $$[k-\varepsilon,k+\varepsilon]$$, and we would like to find the witnessing subset. Is this NP-Hard?

Any links/resources (papers/books/etc) that discuss this problem would also be appreciated. Thank you.

• If $\epsilon<1$, then the error variant coincides with the original SUBSET SUM problem. If $\epsilon$ is some fixed real number, then the error variant coincides with a scaled version of SUBSET SUM. Hence all these variants are NP-hard. Mar 11, 2022 at 10:54
• Oh shoot I forgot a key detail; in this variant, input comes from positive reals, not positive integers. Mar 11, 2022 at 15:51
• For 1. Integers is a subset of real numbers (this is the point of Gamow). For 2. NP-hardness is defined for decision problems not for witness extraction but I understand what you mean. Let us suppose that you have a witness extraction algorithm that run in polynomial time $P(n)$ for an input of size $n$ that has a sum in $[k-\epsilon;k+\epsilon]$. You can run this algorithm on any instance and stop it after $P(n)$ and check whether the witness is correct (this supposes that you know $P$). Mar 11, 2022 at 16:13
• If the input is from the reals, is this still on a Turing machine model with numbers in floating point, or is it some real-valued machine that can do additions in O(1) time, etc.?
– Jake
Mar 11, 2022 at 18:44
• @jake the latter Mar 11, 2022 at 19:12