I want to prove the NP-hardness of my problem P in scheduling. I was trying with Partition, 3-Partition and Subset product, But neither was successful.

Now, I can reduce a problem, say PRODUCT-2-PARTITION to P, but I am not sure whether such problem is $NP$-complete or not?

The problem PRODUCT-2-PARTITION is as follows:

Given $n$ integers. Can we partition them into $n/2$ subsets, where each subset contains exactly $2$ integers, and the product of the elements of any subset is equal to a given value $B$?

  • $\begingroup$ This can be solved by blossom algorithm for general matching. $\endgroup$ – Thinh D. Nguyen Oct 18 '18 at 8:07

Denote these integers by $x_1\ge x_2\ge\cdots\ge x_n$. We assume these integers are all positive (it is not hard to revise the following algorithm for instances including both positive and negative integers).

In a valid solution, the greatest element must match the smallest element. Otherwise, say $x_1$ matches $x_i$ where $x_i>x_n$, and $x_n$ matches $x_j$, then $B=x_1x_i>x_1x_n\ge x_jx_n=B$, a contradiction. Hence a valid solution can only be $\{x_1,x_n\},\{x_2,x_{n-1}\},\ldots$ We only need to check whether this partition is valid, i.e. whether $x_1x_n=x_2x_{n-1}=\cdots=B$.

  • $\begingroup$ Yes, due to number-theoretic nature, this is much simpler to blossom algorithm. $\endgroup$ – Thinh D. Nguyen Oct 18 '18 at 8:41
  • $\begingroup$ Great. That is right. What if the partitions have three elements? Similar to 3-Partition problem? $\endgroup$ – Mostafa Oct 18 '18 at 9:07
  • $\begingroup$ @Mostafa Yes, you can reduce it from 3-Partition by transforming each integer $x$ to $2^x$. $\endgroup$ – xskxzr Oct 18 '18 at 9:10

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.