0
$\begingroup$

Original Problem

Given a set $N=\{a_1,...,a_{n}\}$ with $n$ positive numbers and $\sum_i a_i=1$, find a subset whose sum is $x_*$, where $x_*$ is a known fixed irrational number and $x_*\approx 0.52$.

I proved its hardness by the following arguments.

Instance

Given a set $N=\{a_1,...,a_{n+2}\}$ with $n+2$ numbers where

  • $a_1,...,a_n$ are positive and rational
  • $\sum_{i=1}^n a_i = .02$
  • $a_{n+1}=x_*-0.01$
  • $a_{n+2}=0.99-x_*$

determine whether we can find a subset of $N$, such that the sum of the subset is $x_*$. .

NP-complete

  • Since 𝑥∗ is irrational, the desired subset cannot contain both of the last two numbers.

  • Since the sum of any subset not containing the n+1st element is smaller than 𝑥∗, the desired subset must contain the n+1st element.

  • The remaining question is to find a subset of the first n numbers whose sum is .01

So the original problem is NP-complete.

My problem

Someone argued that since $x_*$ is irrational, I can't store irrational numbers in a machine properly and my proof is not correct. How to address it?

| cite | |
$\endgroup$