patternMinor
Conditions for Linear Diophantine Equations to always have a solution
Viewed 0 times
conditionslinearequationsalwaysfordiophantinesolutionhave
Problem
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?
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?
Solution
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).
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).
Context
StackExchange Computer Science Q#76840, answer score: 3
Revisions (0)
No revisions yet.