# Is this an $NP$-complete problem: Product-2-Partition

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

• This can be solved by blossom algorithm for general matching. – 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$$.
• @Mostafa Yes, you can reduce it from 3-Partition by transforming each integer $x$ to $2^x$. – xskxzr Oct 18 '18 at 9:10