1
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Many thanks! I did not major in CS. Your comments broaden my horizons! $\endgroup$ – GPI Feb 26 at 11:33
  • $\begingroup$ Is the following problem well-defined with regarding to its computation complexity? Given a set $N=\{a_1,...,a_{n}\}$ with $n$ numbers where ​$a_1,...,a_n$ are positive and rational. Determine whether we can find a set $S\subseteq N$, such that $|\beta \sum_{i\in S}a_i-\sum_{j\in N\setminus S} a_j|$ is minimized, where $\beta$ is fixed and irrational. $\endgroup$ – GPI Feb 26 at 11:55
  • 1
    $\begingroup$ @GPI That problem ("Determine whether there exists a set that minimizes ...") is trivial since there always exists such a set; we can always answer "YES" regardless of the input. $\endgroup$ – Tom van der Zanden Feb 26 at 12:17
  • 1
    $\begingroup$ @GPI The complexity of actually finding the set could be high and outside of NP. Suppose $\beta$ is the irrational number, where the $i$th digit of the decimal expansion of $\beta$ is $1$ if the $i$th Turing machine halts and $0$ otherwise (the set of Turing machines is countable so we can fix some correspondence of TMs to integers). The associated problem for $\beta$ is undecidable. $\endgroup$ – Tom van der Zanden Feb 26 at 12:21
  • 1
    $\begingroup$ @GPI Generally you should ask follow-up questions as a new question, not as comments; it's hard to answer in the space of a comment. However, consider taking a step back from irrational numbers until you have a good understanding of basic complexity theory. With every question you are asking, you are opening an even more esoteric can of worms. Irrational numbers are very weird and are only good for getting into technicalities. $\endgroup$ – Tom van der Zanden Feb 26 at 16:29
6
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you a lot! It is corrected now! $\endgroup$ – GPI Feb 26 at 11:34
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Even though the last one was correct, I edited it and gave a better proof. $\endgroup$ – User Not Found Feb 26 at 3:47
  • 1
    $\begingroup$ Ah, he is mentioning the fact that you can't store irrational numbers in a machine properly. Since all the numbers that you store in a computer will comprise of bits and will evaluate to a rational number.... wich will turn out to be an approximation of the irrational number you had in mind. $\endgroup$ – User Not Found Feb 26 at 3:54
  • 1
    $\begingroup$ So assuming all the numbers you mentioned are rational, even then the problem remains NP-Complete $\endgroup$ – User Not Found Feb 26 at 3:55
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you. Tthe elements in $N$ are arbitary real numbers and $x_*$ is a fixed constant. $\endgroup$ – GPI Feb 26 at 7:37
  • 1
    $\begingroup$ @GoodMath, very good, so my comments in the second paragraph apply -- that's not a well-defined problem statement. You can't represent arbitrary real numbers finitely. I agree with the criticism. $\endgroup$ – D.W. Feb 26 at 8:42
  • $\begingroup$ Thank you a lot! $\endgroup$ – GPI Feb 26 at 11:34
  • $\begingroup$ I am a novice in this field. I would like to ask an additional question. Thank you in advance: Given a set $𝑁=\{𝑎_1,⋯,𝑎_𝑛\}$ where all $𝑎_𝑖$s are rational positive numbers and $\sum_{i\in N}a_i=1$, find a subset 𝑆⊆𝑁 such that $(\sqrt{2\sum_{i\in S}a_i}-1)^2$ is minimized. Do the existences of $\sqrt{2}$ and $\sqrt{\cdot}$ make the problem not well-defined with regrading to complexity? If well-defined, it is NP-hard, right? $\endgroup$ – GPI Feb 26 at 15:53
  • 1
    $\begingroup$ @GPI, it is well-defined. I don't know whether it is NP-hard. That would need a proof. $\endgroup$ – D.W. Feb 26 at 17:26
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ What is the role of $p$? If I just need to pick "a prime" I could just pick $p=2$ but I don't see how that changes anything (since I could transform a by multiplying everything with $2$ and then feeding it to your reduction). $\endgroup$ – Tom van der Zanden Feb 27 at 12:22

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.