NPC Pill #4: Square-Free Subset Product

While thinking about possible answers to the question “Listing of strongly NP-complete problems” I came up with this simple numeric strongly NP-complete problem:

[SQUARE-FREE SUBSET PRODUCT] Given $3N$ integers, find $N$ of them whose product is square free.

I didn’t find it anywhere, so it can be somewhat “original”.

Proof sketch: starting from a an Exact Cover by 3 sets (X3C) instance (strongly NPC) label each element of the universe with a distinct prime (you can generate $3|X|$ of them in polynomial time); then convert every triple $(x,y,z)$ of the subsets to $xyz$.

It obviously resembles the better known SUBSET PRODUCT (which is not strongly NPC due to the presence of the target product $B$, see David S. Johnson: The NP-Completeness Column: An Ongoing Guide. 393-405).

It can also be hacked a little bit to get other variants, like:

* Given $3N$ integers, find $N$ of them whose product is a perfect $21$-th power;
* Given $N$ integers, find a subset whose product is the $3N$-th primorial (kind of cheating :-).

If you find that SQUARE-FREE SUBSET PRODUCT has been used/defined in some paper (possibly under another name), let me know!

Leave a Reply

Your email address will not be published. Required fields are marked *