1
$\begingroup$

Garey and Jhonson mentions that a 3-SAT Problem can be transformed to another NP-Complete Problem - Simultaneous incongruences (AN2):

Given a collection $[(a_1,b_1),…,(a_n,b_n)]$ of ordered pairs of positive integers with $a_i≤b_i$ for $1≤i≤n$, is there an integer $x$ such that for all $i$, $x≢a_i(mod\ b_i)$?

But I am struggling with the transformation and not much clue how to go about it nor can find any literature on it. Thus, needed help with the transformation?

$\endgroup$
2
$\begingroup$

Given a SAT instance on $n$ variables, find $n$ relatively prime integers $p_1,\ldots,p_n \geq 2$ of polynomial size (for example the first $n$ primes). The idea is to encode the value of variable $x_i$ as $x \bmod{p_i}$. The first step is to ensure that the variables are indeed binary. To this end, for each $i$ and for each $2 \leq a < p_i$, we add the constraint $x \not\equiv a \pmod{p_i}$.

Each clause involving $p_i,p_j,p_k$ corresponds to one forbidden value of $x \bmod{p_ip_jp_k}$ via the Chinese reminder theorem. For example, consider the clause $x_i \lor x_j \lor \lnot x_k$. Find the value $0 \leq a < p_ip_jp_k$ which satisfies $a \equiv 0 \pmod{p_i}$, $a \equiv 0 \pmod{p_j}$, and $a \equiv 1 \pmod{p_k}$. Add the constraint $x \not\equiv a \pmod{p_ip_jp_k}$.

The resulting system is completely equivalent to the original 3SAT instance.

$\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.