2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

If you want to go further and prove your problem is NP-complete, simply notice that it must be NP because it's easy to check an answer. Therefore it's NP-complete.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – 1-approximation Feb 22 '16 at 20:35
  • 1
    $\begingroup$ 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. $\endgroup$ – Robert Israel Feb 23 '16 at 1:07

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.