NP-hard or not: partition with irrational input or parameter

Question

See some related questions in Cont: NP-hard or not: partition with irrational input or parameter

Given a set $N=\{a_1,...,a_{n}\}$ with $n$ positive numbers and $\sum_i a_i=1$, find a subset $S\subseteq N$ such that $F(\sum_{i\in S} a_i;\alpha)$ is maxmized, where $F(\cdot;\alpha)$ is a known fixed function with parameter as $\alpha$.

Method 1.

To prove the complexity of the problem above, I set $\alpha=1$. Then $x_*=\textbf{argmax}_{0\le x\le 1} F(x;\alpha=1)$ can be calculated, which is an irrational number and $x_*\approx 0.52$.

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 = 0.02$,
• $a_{n+1}=x_*-0.01$, and
• $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 $x_*$ is irrational, the desired subset cannot contain both of the last two numbers.
• Since the sum of any subset not containing the $(n+1)$th element is smaller than $x_∗$, the desired subset must contain the $(n+1)$th element.
• The remaining question is to find a subset of the first $n$ numbers whose sum is 0.01

So the original problem is NP-complete.

Criticism

Since $x_*$ is irrational, I can't store irrational numbers in a machine properly and my proof is not correct.

Method 2

Set $\alpha$ with some value which may be irrational, such that $\textbf{argmax}_{0\le x\le 1} F(x;\alpha)$ is rational. Then repeat the process in method 1 and the problem can be reduced from a subset sum problem. This proof does not have the issue of encoding irrational numbers.

Answer 1

It is impossible to say anything about the NP-hardness of this problem because the input encoding is not defined in sufficient detail. To be able to discuss NP-hardness to begin with, we need to know how problem instances are encoded as binary strings. Changing the encoding of a problem can change whether it is NP-hard or not (e.g., Subset Sum is polynomial if the input is encoded in unary and NP-hard if the input is encoded in binary).

Since we are working with numbers, we need to specify how the numbers are encoded in the input. A small problem with irrational numbers is that it is impossible to encode them as binary strings. Since there are uncountably many irrational numbers and only countably many binary strings, we cannot encode every irrational number as a binary string.

The most standard way of assuming number encodings is as binary numbers, but this only allows encoding of integers or rational numbers. We can of course extend the set of number we can encode to include some irrational numbers, such as agreeing on an encoding for the square root of a rational number, or agreeing on an encoding for some special constants (such as $\pi$). However, we are always limited to some countable subset of the irrational numbers.

Let's say you pick an encoding in which, by sheer serendipity, it is possible to represent both $x_*-0.01$ and $0.99-x_*$. Then the problem is NP-hard by the (somewhat sloppy) reduction you just gave (unless you use some form of unary encoding).

Suppose $x_*$ is a really annoying irrational number which you cannot represent in the problem's encoding. Suppose furthermore that the encoding scheme is closed under addition and subtraction (e.g., if it can represent $x$ and $y$, it can also represent $x+y$ and $x-y$). Then the problem is not NP-hard, and is polynomial-time solvable. This is because every instance is a NO-instance, since it is never possible to write $x_*$ as a sum of numbers in the instance.

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?

You should address this by specifying an encoding scheme for your problem instances.

Answer 2

The problem you have stated probably contains an error:

Given a set $N$ with $n+2$ numbers,​ such that the first $n$ numbers are positive and rational with sum $1$, the $(n+1)$st number is $\sqrt{2}$, and the $(n+2)$nd number is $2 - \sqrt{2}$, determine whether there is a subset of $N$ such that the sum of the subset is $3/2$.

The answer is that there is never any such subset. Either the subset includes $\sqrt{2}$ and $2 - \sqrt{2}$, or neither. If it includes neither, then the sum is less than or equal to $1$. If it includes both, then the sum is greater than or equal to $2$. So the sum of the subset will never be $3/2$.

Answer 3

It is a well known fact that subset sum is NP-Complete (http://www.cs.cornell.edu/courses/cs4820/2018fa/lectures/subset_sum.pdf)

However subset sum requires you to find a subset which sums up to a required number, say $a$ or even $0$. Your problem is slightly different. Note that since $x_*$ is irrational, you need to use either $a_{n+1}$ or $a_{n+2}$ or both.

Note here that if you use both $a_{n+1}$ and $a_{n+2}$, you already exceed $x_*$ and hence you can't use both.

Supoose you use only $a_{n+2}$. The you will have $0.99-x_*+$ some combination of $a_i$'s giving you $x_*$, which would mean that $2x_*$ is a rational number-not possible.

Hence you have to find a combination of the $a_i$'s +$a_{n+1}$ giving you $x_*$. Check that this is exactly the subset sum problem, making it NP-Complete.

Answer 4

I agree with the criticism you got. I think it is more serious than stating that the proof is incorrect; I think the claim (of what you are trying to prove) is unclear or not well-defined. Obviously, we can't ask whether the claim is true or false or whether there is a valid proof for it if the claim isn't well-defined.

So why is the claim not well-defined? It's because the problem isn't well-defined. First, you don't specify how the numbers in $N$ will be represented. If the numbers are integers, the default assumption is to assume they're represented in binary. If they are rational numbers, the default assumption is the rational number $a/b$ is represented as a pair of integers $a,b$, where $a,b$ are chosen so that $b>0$ and $\gcd(a,b)=1$. But for arbitrary numbers that might be irrational, it's not clear what you have in mind. There is no way representation that lets you represent all irrational numbers in a finite amount of space: there are uncountably many irrational numbers, but only countably numbers that can be finitely represented. So, to make the problem well-defined, you have to specify how the numbers will be represented, which will implicitly pose constraints on the numbers so that not all irrationals are actually possible.

Second, it's not clear to me whether $x_*$ is part of the input, or whether it is a fixed constant. This might affect the complexity of the problem as well.

Finally, as a bonus, there's a flaw in your reduction proof. A correct reduction proof must show that for any instance of subset-sum, you can solve that instance using an algorithm for the original problem. You haven't shown that, since you only consider a particular special case of subset-sum.

Answer 5

Take any instance of Subset Sum, i.e. a (multi)set of integers $A = \{a_1, \dotsc, a_n\}$ and a target sum $S$ (Is there a (multi)subset of $A$ that sums $S$?), and create an instance of your problem by picking a prime $p$ and an irrational $0 < i < 1$, propose the problem with $A' = \{a_1 / p, \dotsc, a_n / p, i, 1 - i\}$, $S' = S / p + 1$. It is clear that the modified problem has a solution if and only if the original one has, it is a bona fide polynomial reduction if the representation of $i$ is finite (like $\sqrt{2} - 1$). Thus your problem is NP-hard. If it is also in NP depends on how the (general) irrational number is represented. As there are uncountable irrationals and only a countable number of finite formulas, not all instances can be represented in finite terms.