2
$\begingroup$

Integer Linear Programming (ILP) is NP-complete. However, there are special instances that can be solved in polynomial time. I am curious about the following integer program (IP) with equations and inequalities in $y_i, c_i, x \in \mathbb Z$ of the following form:

$$\begin{align*} A_i + B_i y_i+ c_i &= x \\ c_i^2 &> 0\\ c_i^2 &< B_i^2\\ y_i &\geq 0 \end{align*}$$

where $A_i, B_i \in \mathbb N^+$ are given. I wasn't able to find much on this special case. Anyone please?

$\endgroup$
  • $\begingroup$ This problem reduces to testing whether there is a solution to the system of simultaneous equations $x \not\equiv A_i \pmod{B_i}$. (WLOG we can assume $B_i \ge 2$ for all $i$. If not, negate the negative $B_i$'s; and if $B_i=0$ or $B_i=1$ for any $i$, there is no solution.) $\endgroup$ – D.W. Apr 4 '18 at 17:37
  • $\begingroup$ Thanks. I understand the reduction. The problem it reduces to is it difficult to solve (NPC)? If its NPC (i am guessing) can we have some minimum relaxation so it can be solved in P time in worst case ? $\endgroup$ – J.Doe Apr 4 '18 at 17:47
  • $\begingroup$ $c_i^2 > 0$ is equivalent to $c_i \neq 0$. How is this an integer program? $\endgroup$ – Rodrigo de Azevedo Apr 6 '18 at 8:48
  • $\begingroup$ How many $c_i$'s do you have? $\endgroup$ – Rodrigo de Azevedo Apr 6 '18 at 9:10
3
$\begingroup$

It is NP-hard, by reduction from 3SAT.

Your problem is equivalent to the following: given a system of inequalities of the form $x \not\equiv A_i \pmod{B_i}$, where the $A_i,B_i$ are given, test whether any solution exists. (Why? If $0 < c_i^2 < B_i^2$ then $c_i \not\equiv 0 \pmod{B_i}$, and vice versa.)

Now 3SAT can be reduced to this problem (satisfiability of a system of inequalities), so it follows that this problem is NP-hard. Here's how the reduction works.

Let $\varphi$ be a 3SAT instance, with variables $v_1,\dots, v_n$. Let $p_1,\dots,p_n$ be the first $n$ primes. Add inequalities of the form $x \not\equiv 2 \pmod{p_i}$, $x \not\equiv 3 \pmod{p_i}$, ..., $x \not\equiv p_i-1 \pmod{p_i}$ for each $i$, forcing $x$ to be either 0 or 1 modulo each prime. Now, suppose we have a clause $v_i \lor v_j \lor v_k$. This translates to an inequality $x \not\equiv 0 \pmod{p_i p_j p_k}$. The clause $v_i \lor \neg v_j \lor v_k$ translates to $x \not\equiv \alpha \pmod{p_i p_j p_k}$ where $\alpha$ is the unique value such that $\alpha \equiv 0 \pmod{p_i}$, $\alpha \equiv 1 \pmod{p_i}$, and $\alpha \equiv 0 \pmod{p_i}$ (you can find $\alpha$ using the Chinese remainder theorem). And so on -- in this way, each clause can be translated into an inequality.

Finally, there exists a value $x$ that satisfies all of these inequalities if and only if there exists an assignment that satisfies $\varphi$. (Why? $x\equiv 1 \pmod{p_i}$ corresponds to setting $v_i$ to true, and $x\equiv 0 \pmod{p_i}$ corresponds to setting $v_i$ to false. You can then verify equivalence between clauses and inequalities.) Since the resulting system has size polynomial in $n$, this gives a polynomial-time reduction from 3SAT to your problem.

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