1
$\begingroup$

I want to prove the NP-hardness of some problem P in scheduling theory. 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$?

$\endgroup$
1
  • $\begingroup$ This can be solved by blossom algorithm for general matching. $\endgroup$ Oct 18, 2018 at 8:07

1 Answer 1

1
$\begingroup$

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$.

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