1
$\begingroup$

How can we prove that the following problem $A$ is NP complete?

Given a set of integers $S={a_1, ..., a_n}$ and a number $D$, is it possible to find disjoint sets $S_1, S_2, S_3, S_4$ such that $S_1 \cup S_2 \cup S_3 \cup S_4=S$ and

$$ -\sum_{j=1}^{4}\frac{\sum_{a_i \in S_j}a_i}{\sum_{a_i \in S}a_i}\log_2(\frac{\sum_{a_i \in S_j}a_i}{\sum_{a_i \in S}a_i})\geq D$$

I was thinking on using some NP complete problem $B$ and showing that $B \leq_P A$, but I can't figure out what reduction would work.

Here is what I tried (simplified the problem to 2 sets): Given a set $S$ of n elements, I tried to prove that $S \in \text{Partition-Problem} \iff \langle S, 1 \rangle \in A$. If $S$ is an instance of the partition problem, it means there are 2 subsets in $S$ that have the same sum ($n/2$). Therefore the expression in $A$ (with 2 sets instead of 4) evaluates to $-\log_2 (1/2)=1$. Then proving $S \in \text{Partition-Problem} \Rightarrow \langle S, 1 \rangle \in A$ is trivial. However I am still stuck at proving the $\Leftarrow$ part.

$\endgroup$
  • $\begingroup$ What have you tried? What reduction partners (candidates for $B$) have you tried so far, and where did you get stuck? See cs.stackexchange.com/q/1240/755. Have you tried solving this with 4 replaced with 2? $\endgroup$ – D.W. Mar 11 '17 at 7:36
  • $\begingroup$ @D.W. I considered 4-sat and 4-coloring as there might be a way to map their construct to the problem, but can't figure out what gadget to use. Finally I also thought of a modified version of the subset sum problem, like a 4-subset sum problem (are there 4 subsets whose sum is 0 and whose union equals S). However this is as far as I've gotten because I really can't think of anything specific other than the general structure that links this problem to other NP complete ones. The log and inequality is maybe what's confusing me $\endgroup$ – user1354784 Mar 11 '17 at 18:12
  • $\begingroup$ I recommend you start by replacing 4 by 2 and see if you can solve that; see if you can think of any suitable reduction partners (with 2, not 4). Finally, do you recognize anything about that expression? Are you familiar with (Shannon) entropy? That might help you. If you choose $D$ appropriately, can you get some intuition for what sort of requirement that constraint is imposing (what it's pushing you to make the sets look like)? You might want to work through some examples to get a better intuition/feeling for it. Then, please edit the question to show what you tried. $\endgroup$ – D.W. Mar 11 '17 at 18:24
  • $\begingroup$ Still thinking about it so I will update once I think of more, but just got an idea. I think we could reduce "Are there 4 subsets that have the same sum" to this problem, since if the elements in S sum to n, then the sum of each subset must be n/4, so the fractions each give (n/4)/n=1/4, then -sum from 1 to 4 of 1/4log(1/4)=-log(1/4)=2, so maybe checking with D=2 would work. However I still need to convince myself that >=2 does not occur in other cases. $\endgroup$ – user1354784 Mar 11 '17 at 18:57
  • 1
    $\begingroup$ Great. Now you just need to prove the $\Leftarrow$ part. Work through some examples with the binary entropy function; what is the range of possible values for $p$ so that $-p \log_2 p -(1-p)\log_2(1-p)$ will be $\ge 1$? $\endgroup$ – D.W. Mar 11 '17 at 23:22
0
$\begingroup$

Let's say that the numbers $a_1,\ldots,a_n$ are non-negative, and sum to $A$. They induce a probability distribution on $\{1,\ldots,n\}$, in which the probability of $i$ is $a_i/A$.

Given a partition $S_1,S_2,S_3,S_4$, let $I$ be a random variable distributed as above, and let $X$ be the index of the set to which $I$ belongs (so $X \in \{1,2,3,4\}$). Your condition then reads $$ H(X) \geq K, $$ where $H(\cdot)$ is the entropy function.

This suggests choosing $K = 2$, since we know that $H(X) = 2$ iff $\Pr[S_1] = \Pr[S_2] = \Pr[S_3] = \Pr[S_4]$.

We can now describe a reduction from PARTITION to your problem. Given an instance $b_1,\ldots,b_m$ of PARTITION, where $b_1,\ldots,b_m$ are non-negative integers summing to $B$, create an instance of your problem by adding two copies of $B/2$, and by taking $K=2$. The list $b_1,\ldots,b_m,B/2,B/2$ can be partitioned into four parts with equal sum (i.e., $H(X) \geq 2$) if $b_1,\ldots,b_m$ can be partitioned into two parts with equal sum.

$\endgroup$

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.