N. T. Kogabaev, “The np-completeness of the consistency problem for systems of Diophantine equations over finite configurations”, Sibirsk. Mat. Zh., 2025, Volume 66, Number 3,Pages <nobr>450

The np-completeness of the consistency problem for systems of Diophantine equations over finite configurations

N. T. Kogabaev^ab

^a Sobolev Institute of Mathematics, Novosibirsk, Russia
^b Novosibirsk State University, Novosibirsk, Russia

Abstract: Studying finite systems of Diophantine equations over finite configurations, we prove that the consistency problem for such systems is NP-complete.

Keywords: configuration, incidence, system of equations, nondeterministic Turing machine, NP-complete problem.

UDC: 510.522+514.146

Received: 14.11.2024
Revised: 14.11.2024
Accepted: 25.04.2025

DOI: 10.33048/smzh.2025.66.310