Complexity of the consistency problem for systems of Diophantine equations over finite bipartite graphs
Complexity of the consistency problem for systems of Diophantine equations over finite bipartite graphs
(Russian, English abstract)
Siberian Electronic Mathematical Reports, 23, 1, pp. 266-288 (2026)
Abstract:
We study finite systems of Diophantine equations over finite bipartite graphs. In 2021, A.V. Il'ev and V.P. Il'ev proposed a deterministic polynomial-time procedure for verifying the consistency of such systems. We construct a counterexample to show that their procedure works incorrectly and prove that the consistency problem for such systems is in fact NP-complete.
Keywords: bipartite graph, system of equations, nondeterministic Turing machine, NP-complete problem