2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

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.