NP-hard or not: partition with irrational input or parameter 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.
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$.