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.