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

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

Когабаев Н. Т.

УДК 510.522+514.146 
DOI: 10.33048/smzh.2025.66.310


Аннотация:

Изучаются конечные системы диофантовых уравнений над конечными конфигурациями. Доказано, что проблема совместности таких систем является NP-полной.

Литература:
  1. Даниярова Э. Ю., Мясников А. Г., Ремесленников В. Н. Алгебраическая геометрия над алгебраическими системами. Новосибирск: Изд-во СО РАН, 2016.
     
  2. Ильев А. В., Ремесленников В. Н. Исследование совместности систем уравнений над графами и нахождение их общих решений // Вестн. Омск. ун-та. 2017. № 4. С. 26–32.
     
  3. Ильев А. В., Ильев В. П. Алгоритмы решения систем уравнений над различными классами конечных графов // Прикл. дискрет. математика. 2021. № 54. С. 89–102.
     
  4. Ильев А. В. Исследование систем уравнений над различными классами конечных матроидов // Сиб. электрон. мат. изв. 2022. Т. 19, № 2. С. 1094–1102.
     
  5. Никитин А. Ю., Рыбалов А. Н. О сложности проблемы разрешимости систем уравнений над конечными частичными порядками // Прикл. дискрет. математика. 2018. № 39. С. 94–98.
     
  6. Никитин А. Ю. Алгебраическая геометрия и алгоритмы в классе частично упорядоченных множеств // Вестн. Омск. ун-та. 2024. Т. 29, № 1. С. 23–32.
     
  7. Когабаев Н. Т. Об системах диофантовых уравнений над конечными конфигурациями // Сиб. мат. журн. 2023. Т. 64, № 2. С. 321–338.
     
  8. Hughes D. R., Piper F. C. Projective planes. New York, Heidelberg, Berlin: Springer-Verl., 1973.
     
  9. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.
     
  10. Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ, 2-е изд.. М.: Вильямс, 2005.

 Работа выполнена за счет гранта Российского научного фонда, проект № 23-11-00170, https://rscf.ru/project/23-11-00170.


Когабаев Нурлан Талгатович (ORCID 0000-0002-3940-0824)
  1. Институт математики им. С. Л. Соболева СО РАН, 
    пр. Академика Коптюга, 4, Новосибирск 630090
  2. Новосибирский государственный университет, 
    ул. Пирогова, 1, Новосибирск 630090

E-mail: kogabaev@math.nsc.ru

Статья поступила 14 ноября 2024 г. 
После доработки — 14 ноября 2024 г.
Принята к публикации 25 апреля 2025 г.