1
$\begingroup$

This is a follow up to the previous Question: Conditions for Linear Diophantine Equations to always have a solution

It was established in the above's answer that obtaining or testing for the existence of an solution of an ILP in $\mathbb N$ is an NP Hard Problem. This in turn makes obtaining solution for a (LDP) Linear Diophantine Problem (where $v$ > $n$) in $\mathbb N$ an NP-hard Problem too.

Now given the restricted ILP Problem with an additional constraint:

The number of unique pure constants (i.e. ones without variables, denoted by $c_0 below) permitted in any system has an fixed upper Bound (say 2) where equations are of the form:

$c_0 + c_1 x_1 + \dots + c_k x_k \ge 0$

Is this restricted version of ILP still NP-hard?

$\endgroup$
2
$\begingroup$

Yes, it's still NP-hard. Suppose the two allowed values for $c_0$ are 0 or 1, and that you're allowed to have equations of the form

$$c_0 + c_1 x_1 + \dots + c_k x_k = 0$$

as well (not just inequalities). Suppose that we wish we could use the constant 17. We can introduce new variables $z_1,\dots,z_6$, add the equalities below, and replace all occurrences of 17 with $z_6$.

$$\begin{align*} 1 - z_1 &= 0\\ 0 + 2 z_1 - z_2 &=0\\ 0 + 2 z_2 - z_3 &=0\\ 0 + 2 z_3 - z_4 &=0\\ 0 + 2 z_4 - z_5 &=0\\ 0 + z_1 + z_5 - z_6 &=0 \end{align*}$$

Notice how the above equations force $z_1=1$, $z_2=2$, $z_3=4$, $z_4=8$, $z_5=16$, and $z_6=17$.

Of course there's nothing special about 17; you can do this for any other number as well. In general, if you have any constant $\kappa$ you wish you could use, you can find an addition chain for $\kappa$, then use that to introduce temporary variables $z_1,\dots,z_t$ that force $z_t=\kappa$, then replace all occurrences of the constant $\kappa$ with the variable $z_t$.

In this way you can eliminate all constants other than 0 or 1 for $c_0$. The length of the addition chain for $\kappa$ will be at most $2 \lceil \lg \kappa \rceil$, so the number of extra variables and equalities added is not too large (and in particular is polynomial in the size of the original problem), so this increases the size of the instance by at worst a polynomial factor.

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