2
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ 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. $\endgroup$
    – Gamow
    Commented Mar 11, 2022 at 10:54
  • $\begingroup$ Oh shoot I forgot a key detail; in this variant, input comes from positive reals, not positive integers. $\endgroup$
    – CSSTUDENT
    Commented Mar 11, 2022 at 15:51
  • $\begingroup$ 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$). $\endgroup$
    – Louis
    Commented Mar 11, 2022 at 16:13
  • $\begingroup$ 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.? $\endgroup$
    – Jake
    Commented Mar 11, 2022 at 18:44
  • $\begingroup$ @jake the latter $\endgroup$
    – CSSTUDENT
    Commented Mar 11, 2022 at 19:12

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.