On polynomial-time solvable linear Diophantine problems (Q2332795): Difference between revisions

Let \(A=(B|N)\in \mathbb Z^{m\times n},m\leq n\) with a non-singular part \(B\in \mathbb Z^{m\times m}\) and \(b\in\mathbb Z^m\). The author considers nonnegative integer solutions of the system \(Ax=b\). Denote by \(\ell_N\) the Euclidean length of the longest column in the matrix \(N\). Let \(\mathcal C_B\) be the cone generated by the columns of the matrix \(B\), denote by \(\mathcal C_B(t)\) the affine cone of points in \(\mathcal C_B\) at Euclidean distance \(\ge t\) from the boundary of \(\mathcal C_B\). Denote by \(\gcd(A)\) the greatest common divisor of all \(m\times m\) subdeterminants of \(A\). The author proves that if \[b\in\mathbb Z^m\cap \mathcal C_B\left(\ell_N \left( \frac{|\det(B)|}{\gcd(A)}-1\right)\right)\] then there exists a polynomial-time algorithm which finds a nonnegative integer solution to the system \(Ax=b\) or determines that no such solution exists.