2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ i think we cannot beat $n^m$ for this problem at large $b$. $\endgroup$ – T.... Jun 4 '16 at 9:51
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Andrew Morgan Jul 13 '16 at 8:15

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.