Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
