Сложность проблемы совместности систем диофантовых уравнений над конечными двудольными графами
Сложность проблемы совместности систем диофантовых уравнений над конечными двудольными графами
Сибирские электронные математические известия, 23, 1, стр. 266-288 (2026)
Аннотация:
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.
Ключевые слова: bipartite graph, system of equations, nondeterministic Turing machine, NP-complete problem