0
$\begingroup$

It is well known that the conventional subset sum problem with integers is NP-complete. What if the array elements can be any real numbers and also target sum can be any real number? Is it NP-complete still or harder (NP-hard)?

$\endgroup$
  • 1
    $\begingroup$ What model of computation are we talking about here? Most real numbers cannot be encoded as a finite string. $\endgroup$ – dkaeae Jun 11 at 16:04
1
$\begingroup$

What model of real numbers are you using? If it's something like floating point, where everything is really rational, just multiply through by a common denominator and you're back in the world of integers. The bit-length is only polynomially larger than the ones you started with (the common denominator is at most the product of $n$ $n$-bit numbers, so it has at most $n^2$ bits), so nothing has changed, complexity-wise.

Beyond that, things will get more complicated – can you even tell in polynomial time what numbers are represented by the input?

However, the real-number version is definitely still NP-hard, since it has the integer version as a sub-problem.

$\endgroup$
  • 1
    $\begingroup$ Something does change with the complexity when using rational numbers instead of integers. The problem becomes strongly NP-complete as shown by Wojtczak in this paper: arxiv.org/abs/1802.09465 $\endgroup$ – Pontus Jun 11 at 17:47

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.