“Fuzzy” Chinese Remainder Theorem NP-hard? I have some "fuzzy" congruences like these:
\begin{align} \\ x&amp;\equiv a_1 \mod 3 \text{ with } a_1 \in \{0,1\},\\ x&amp;\equiv a_2\mod 5 \text{ with } a_2 \in \{0,3\},\\x&amp;\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 &lt; 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 &lt; B$.

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

This question is related to another one: &quot;Fuzzy&quot; 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&amp;  \\ y_v+y_u \geq 1 &amp;&amp; \forall uv \in E \\ y_v \geq 0 &amp;&amp; \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.
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 &lt; 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.