# NP-hard or not: partition with irrational input

## 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 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?

Posted on Categories proxies