# How to complete the NP-hardness proof of GENERAL-SQUARE-PRODUCT?

I am interested in the complexity of the following problem:

GENERAL-SQUARE-PRODUCT

INSTANCE: Two sets $A=\{a_1,\ldots,a_n\}$ and $B=\{b_1,\ldots,b_n\}$ of integers, a positive integer $k<n$ and a positive integer $\Delta$.

QUESTION: Is there a subset $S$ of $\{1,\ldots,n\}$ of size $|S|\leq k$ such that $$\left(1+\left(\sum_{i\in S}a_i\right)^2\right)\left(1+\left(\sum_{i\in S}b_i\right)^2\right)\geq\Delta ?$$

Note: $\Delta$ is greater than $1$.

My question is:

• Is this problem NP-hard?

I have proved that the restricted version PRODUCT is NP-hard. (The restricted version consists of non-negative integers and without the squares.)

# Attempt to prove:

Here is my proof which I think incomplete. Can you help me complete it?

I will reduce EQUAL-PARTITION to GENERAL-SQUARE-PRODUCT.

Given an instance $\{x_1,\ldots,x_n\}$ of EQUAL-PARTITION (with $x_i > 0$ and $n$ is even), consider an instance of my problem with $k = n/2$, $\Delta=\left(1+\left(A/2\right)^2\right)^2$ and $A=\sum_{i}x_i$ , and let $a_i=x_i$ for all $i$ and $b_i=2A/n-x_i$ for all $i$.

This is a polynomial time reduction.

Now let us prove that EQUAL-PARTITION is solved $\iff$ GENERAL-SQUARE-PRODUCT is solved.

• "$\Rightarrow$" Suppose that EQUAL-PARTITION is solved. Then there exists $S$ of size $|S|=n/2$ such that $$\sum_{i\in S}x_i=\sum_{i\in S'}x_i=A/2,$$ where $S\cup S'=\{1,\ldots,n\}$ and $S\cap S'=\emptyset$ and $|S|=|S'|=n/2$. Now take the solution to GENERAL-SQUARE-PRODUCT to be $S$. We have \begin{align} &\left(1+\left(\sum_{i\in S}a_i\right)^2\right)\left(1+\left(\sum_{i\in S}b_i\right)^2\right)\geq\Delta\\ \Rightarrow&\left(1+\left(\sum_{i\in S}x_i\right)^2\right)\left(1+\left(\sum_{i\in S}(2A/n-x_i)\right)^2\right)\geq\Delta\\ \Rightarrow&\left(1+\left(\sum_{i\in S}x_i\right)^2\right)\left(1+\left(A-\sum_{i\in S}x_i\right)^2\right)\geq\Delta\\ \Rightarrow&\left(1+\left(A/2\right)^2\right)\left(1+\left(A/2\right)^2\right)=\left(1+\left(A/2\right)^2\right)^2\\ \end{align}
• "$\Leftarrow$" Suppose that GENERAL-SQUARE-PRODUCT is solved. Then there exists $S$ of size $|S|=n/2$ such that \begin{align} \require{overset} &\left(1+\left(\sum_{i\in S}a_i\right)^2\right)\left(1+\left(\sum_{i\in S}b_i\right)^2\right)\geq\Delta\\ \Rightarrow&\left(1+\left(\sum_{i\in S}x_i\right)^2\right)\left(1+\left(\sum_{i\in S}(2A/n-x_i)\right)^2\right)\geq\Delta\\ \overset{(a)}{\Rightarrow}&\left(1+\sum_{i\in S}x_i\right)\left(1+\sum_{i\in S}(2A/n-x_i)\right)\geq\sqrt{\Delta}\\ \Rightarrow&\left(1+\sum_{i\in S}x_i\right)\left(1+A-\sum_{i\in S}x_i\right)\geq\sqrt{\Delta}\\ \Rightarrow&1+ A+A\sum_{i\in S}x_i-\left(\sum_{i\in S}x_i\right)^2\geq\sqrt{\Delta}\\ \Rightarrow&\left(\sum_{i\in S}x_i\right)^2-A\sum_{i\in S}x_i+\sqrt{\Delta}-1- A\leq 0\\ \Rightarrow&X^2-AX+\sqrt{\Delta}-1- A\leq 0\\ \Rightarrow&A/2-\sqrt{A}\leq X\leq A/2+\sqrt{A}\\ \Rightarrow&\left|\sum_{i\in S}x_i-\sum_{i\in S'}x_i\right|\leq\sqrt{A}\\ \end{align}

Finally, can I say that GENERAL-SQUARE-PRODUCT is NP-hard? If not, how to fix this?

where $(a)$ is due to the fact that for all $X>0$, $\left(1+X\right)^2\geq\left(1+X^2\right)$.

# Note:

I asked a restricted version of GENERAL-SQUARE-PRODUCT here where $a_i$ and $b_i$ are non-negative but I get no answers.

Yes, your problem is NP-hard. The proof is by reduction from Subset Sum. Given the Subset Sum problem "does set $S$ have a subset with less than $k$ members summing to $d$?", create an instance of your problem with $A=S$, $B=$"all zeros", $\Delta=1-d^2$, $k=k$. Then the solution to your problem with that $(k,A,B,\Delta)$ will also be the solution to that Subset Sum problem. Subset Sum is NP-complete, therefore your problem is NP-hard.
What do you mean by $\Delta$ "not too big"? If there are at least $\sqrt{\Delta}$ positive $a_i$ or at least $\sqrt{\Delta}$ negative $a_i$, the answer is yes. Otherwise, there are at most $2^{2 \sqrt{\Delta}}$ possibilities for $S \cap \{i: a_i \ne 0\}$ to consider, and each of these cases is easy. So if "not too big" means $\Delta \le k \log(n)^2$ for some $k$, there is a polynomial-time algorithm.
• By $\Delta$ "not too big" I meant to prevent the infeasibility of the problem every time. For example, if $\Delta$ is bigger than some value $\Delta_0$, we could not find any $S$ that satisfy the constraint. Maybe $$\Delta_0=\left(1+\left(\sum_{i=1}^na_i^2\right)^2\right)\left(1+\left(\sum_{i=1}^nb_i^2\right)^2\right)$$ or another value. If I do not have the restriction of $\Delta$ you described, does the proof in the question imply the NP-hardness of the problem? – 1-approximation Feb 22 '16 at 20:35
• So just leave out that statement about "not too big". The presence of easy instances with some values of $\Delta$ does not prevent the problem from being NP-hard, as NP-hardness is about worst-case complexity. – Robert Israel Feb 23 '16 at 1:07