“Fuzzy” Chinese Remainder Theorem NP-hard?

Question

I have some "fuzzy" congruences like these: \begin{align} \\ x&\equiv a_1 \mod 3 \text{ with } a_1 \in \{0,1\},\\ x&\equiv a_2\mod 5 \text{ with } a_2 \in \{0,3\},\\x&\equiv a_3 \mod 7 \text{ with } a_3 \in \{1,2,6\}\\ \end{align} These example moduli would provide a unique solution for $x \bmod lcm(3,5,7)$, if the $a_i$ were fixed. Because the $a_i$ are not fixed, these "fuzzy" congruences lead to $2*3*2=12$ possible solutions for $x \bmod lcm(3,5,7)$.

To reduce the number of possible solutions for $x$, I'm also given an additional constraint $x < B$, which provides an upper bound for $x$.

We can assume that all moduli $m_i$ are primes, so $lcm(m_1,m_2,...,m_n) = \prod_i m_i$. Furthermore each $a_i$ has at most $t$ possible values ($t=3$ in the upper example).

So the general problem is that we are given a constant $t$, primes $m_1,\dots,m_n$, an upper bound $B$, and sets $U_1,\dots,U_m$ (each of size at most $t$), and the goal is to find an integer $x$ such that $x \bmod m_i \in U_i$ for all $i$ and $0 \le x < B$.

Is this problem NP-hard and how can I prove this?

This question is related to another one: "Fuzzy" Chinese Remainder Theorem, but the difference is that here the sets $U_i$ can be arbitrary and need not contain consecutive integers.

My initial approach was to use the k-Vertex-Cover problem for the reduction. I used the Wikipedia Integer programming NP-hardness proof as a template (https://en.wikipedia.org/wiki/Integer_programming#Proof_of_NP-hardness).

Let $G=(V,E)$ be an undirected graph. Define a linear program as follows: \begin{align} \sum_{v \in V} y_v \leq k& \\ y_v+y_u \geq 1 && \forall uv \in E \\ y_v \geq 0 && \forall v \in V \end{align}

I tried to define the Vertices as $a_i$.

But I am unable to transform the $y_v+y_u \geq 1 \text{ , } \forall uv \in E$ (set contains at least one vertex of each edge) inequalities into "fuzzy" congruences.

Answer 1

If you allow arbitrary modulus (so $m_i$ is not required to be prime), your problem is NP-hard. In particular, it is NP-hard to determine whether there exists any valid solution, even without the upper bound $B$.

To prove this, we can reduce 3SAT to the problem. Suppose we have a 3SAT formula $\varphi$ over variables $v_1,\dots,v_n$. Let $p_1,\dots,p_n$ be the first $n$ primes. Then we will associate one congruence per clause of $\varphi$. In particular, the clause $v_i \lor v_j \lor v_k$ corresponds to the congruence

$$x \equiv a \pmod{p_i p_j p_k} \text{ where } a \in U$$

and $U=\{c_{001},c_{010},c_{011},\dots,c_{111}\}$ contains seven values, where $c_{def}$ is the unique constant such that $c_{def} \equiv d \pmod{p_i}$, $c_{def} \equiv e \pmod{p_j}$, and $c_{def} \equiv f \pmod{p_k}$. Do the same for each other clause; e.g., for $v_i \lor v_j \lor \neg v_k$, the set $U$ has the seven values $U=\{c_{000}, c_{010}, c_{011}, c_{100}, c_{101}, c_{110}, c_{111}\}$, and so on.

In this way, we obtain a system of congruences with one congruence per clause of $\varphi$. We don't need an upper bound on $x$ (you can use the trivial upper bound $x < p_1 p_2 \cdots p_n$ if you like). Then there exists a solution to this system of congruences iff the formula $\varphi$ is satisfiable. In particular, a satisfying assignment $(v_1,\dots,v_n)$ for $\varphi$ corresponds to a unique value for $x$ that satisfies all the congruences, namely, the value such that $x \equiv v_i \pmod{p_i}$ for all $i$.

This reduction does require the ability to choose moduluses that are not prime. I don't know if the problem becomes any easier when every modulus is prime.