3
$\begingroup$

Given a set of $n$ linear equations in $v$ integer variables, where $v > n$, we can say that this system of equations will always have an integer solution.

Over $\mathbb N$, is there any such constraint that guarantees that a solution always exists? Or, if not, can it be tested in polynomial time?

$\endgroup$
  • $\begingroup$ In the first paragraph, are you using the Smith normal form? $\endgroup$ – Rodrigo de Azevedo Jun 15 '17 at 19:07
3
$\begingroup$

Short answer: No. Most likely, no useful constraint exists; and it can't be tested in polynomial time.


Detailed answer, with justification: It cannot be tested in polynomial time, unless P = NP. In particular, if you could test for existence of a non-negative integer solution to such a system, you could solve integer linear programming (ILP). Here's how the reduction works:

Suppose we have an ILP instance with variables $x_1,\dots,x_k$. We'll modify it by introducing variables $x_1^+,\dots,x_k^+$ and $x_1^-,\dots,x_k^-$. Then we'll replace each inequality

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

with the equality

$$c_0 + c_1 x_1^+ - c_1 x_1^- + \dots + c_k x_k^+ - c_k x_k^- = y_j$$

and the inequality $y_j \ge 0$, where $y_j$ is a fresh new variable. Thus if the original ILP instance has $k$ variables and $m$ inequalities, the new instance will have $2k+m$ variables, $m$ equalities, and $2k+m$ inequalities $x_i^+ \ge 0$, $x_i^- \ge 0$, $y_j \ge 0$.

This now has the form of your problem, i.e., integer linear diophantine equations where we are looking for non-negative solutions, with $n=m$ linear equations and $v=2k+m$ variables. Note in particular that we are guaranteed to have $v>n$, since we must have $k>0$. Moreover, any solution to the original integer linear programming instance leads to a solution to this diophantine problem (take $x_i^+ = \max(0,x_i)$ and $x_i^- = \max(0,-x_i)$), and conversely, any solution to this diophantine problem leads to a solution to the original ILP instance (take $x_i = x_i^+-x_i^-$). Therefore the derived diophantine problem is equivalent to the original ILP instance.

This reduces ILP to testing existence of a solution to a diophantine problem. Since ILP is NP-hard, it follows that testing existence of solutions to this kind of diophantine problem is NP-hard, too. That means there is not likely to be any polynomial-time algorithm to it (assuming you believe it is unlikely that P = NP).

For similar reasons, you should not expect a useful condition that is necessary and sufficient to ensure that a solution always exists: any such condition must be infeasible to check in the worst case, unless P = NP. You can pick two out of any three: necessary; sufficient; efficiently checkable -- but you can't have all three, assuming P != NP (as many expect).

$\endgroup$
  • $\begingroup$ Thank you for such a detailed answer. Assuming we are limiting the number of unique pure constants (i.e. one involving no variables eg. $c_0$ above in the eqn) in the system to a finite limit (say number of pure constants = 2 or perhaps =1 in any system) would this restricted problem still remain NP Complete? $\endgroup$ – J.Doe Jun 16 '17 at 6:19
  • $\begingroup$ @J.Doe, I don't really understand what you are asking (you are saying the number of unique values of $c_0$, across all inequalities, is limited? Or that's true for all coefficients too?) -- but either way, I don't know the answer. I suspect it's still NP-hard, but it sounds like something to ask as a new question. You might start by asking a new question about whether ILP with a limited number of unique constants is NP-hard. $\endgroup$ – D.W. Jun 16 '17 at 7:10
  • $\begingroup$ Thank you. I meant the number of unique values of $c_0$ across all inequalities is limited. I will ask it as a new Question as a follow up to this one. $\endgroup$ – J.Doe Jun 16 '17 at 7:32
  • $\begingroup$ @D.W. What about the case when there is an additional constraint that in ILP $v - n < C $ where $C$ is a positive integer constant ? $\endgroup$ – TheoryQuest1 Jun 16 '17 at 8:20

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.