Subset product problem

We have $m$ list of integers $L_1,\dots,L_m$ and each list $L_i$ contains $n$ distinct integers $L_i(1),\dots,L_i(n)$.

You are given two integers $a$ and $b$ with $b<a$ and we know $n=O(2^{(\log b)^\alpha})$ and $m=O({(\log b)^\beta})$ for $0<\alpha,\beta<1<\alpha+\beta$.

I want to check to see if I can pick one integer from each list to check if product mod $b$ is $a\bmod b$.

Is there a faster than $n^m$ brute force way to search for this? Is this NP hard (Andrew below sort of gives a pseudo polynomial algorithm)?

Let $S_0=\{1\}$. For $i = 1,...,n$, set $S_i\gets \{xy\mod b : x\in S_{i-1},y\in L_i\}$. Then just check whether $a \in S_n$.

It's obviously correct, since $S_i$ contains the residues which can be expressed as a product of elements, one each from $L_1,\ldots,L_i$.

Just using the definition of $S_i$ to compute it, you get a running time of $O(m n b)$, which is significantly better than brute force when $b$ is smaller than $n^m$.

By replacing the linear sweep by divide and conquer, you might be able to improve the running time even more, though I didn't check. (It will still have a factor of $b$ though.)

• i think we cannot beat $n^m$ for this problem at large $b$. – T.... Jun 4 '16 at 9:51

The meet in the middle approaches that work in subset sum and k-sum should also work here with slight modifications.

It can be solved in $\tilde{O}\left(n^{m/2}\right)$ by constructing two lists $L_1$ and $L_2$ where $L_1$ is all possible products from first $m/2$ lists and $L_2$ is all possible products for last $m/2$ lists. Now we just need to check if there exist $p \in L_1 , q \in L_2$ such that $pq$ is $a\ mod\ b$. This can be done by first computing the inverse of one of the lists (in $\tilde{O}\left(n^{m/2}\right)$) and then checking if there is a common element in $\tilde{O}\left(n^{m/2}\right)$.

We can prove NP-hardness by reduction from subset-product problem. For each integer $x_i, 1 \leq i \leq m$ in subset product instance create a list $(x_i , 1)$ with $n=2$. This only has a solution iff subset product had one(See Andrew's comment). Memebership in NP is trivial.

• To clarify the NP-hardness reduction: If you try the natural-seeming choice of setting $b$ to be the target product and $a$ to be zero, then the reduction fails. Instead, one could pick $b$ to be larger than the product of all $x_i$, and pick $a$ to be the target product from the subset-product instance. – Andrew Morgan Jul 13 '16 at 8:15