Sciact
  • EN
  • RU

NP-полнота проблемы совместности систем диофантовых уравнений над конечными конфигурациями Full article

Journal Сибирский математический журнал
ISSN: 0037-4474
Output data Year: 2025, Volume: 66, Number: 3, Pages: 450-464 Pages count : 15 DOI: 10.33048/smzh.2025.66.310
Tags конфигурация, инцидентность, система уравнений, недетерминированная машина Тьюринга, NP-полная проблема.
Authors Когабаев Н.Т. 1,2
Affiliations
1 им. С. Л. Соболева СО РАН, пр. Академика Коптюга, 4, Новосибирск 630090
2 Новосибирский государственный университет, ул. Пирогова, 1, Новосибирск 630090 E-mail: kogabaev@math.nsc.ru

Funding (1)

1 Russian Science Foundation 23-11-00170

Abstract: Изучаются конечные системы диофантовых уравнений над конечными конфигурациями. Доказано, что проблема совместности таких систем является NP-полной.
Cite: Когабаев Н.Т.
NP-полнота проблемы совместности систем диофантовых уравнений над конечными конфигурациями
Сибирский математический журнал. 2025. Т.66. №3. С.450-464. DOI: 10.33048/smzh.2025.66.310 РИНЦ
Translated: Kogabaev N.T.
The NP-completeness of the consistency problem for systems of Diophantine equations over finite configurations
Siberian Mathematical Journal. 2025. V.66. N3. P.702-714. DOI: 10.1134/S0037446625030103 WOS Scopus РИНЦ OpenAlex
Dates:
Submitted: Nov 14, 2024
Accepted: Apr 25, 2025
Published print: May 30, 2025
Published online: May 30, 2025
Identifiers:
Elibrary: 82386681
Citing: Пока нет цитирований
Altmetrics: