NP-полнота проблемы совместности систем диофантовых уравнений над конечными конфигурациями
NP-полнота проблемы совместности систем диофантовых уравнений над конечными конфигурациями
Сибирский математический журнал, 66, 3, 450-464 (2025)
Аннотация:
Изучаются конечные системы диофантовых уравнений над конечными конфигурациями. Доказано, что проблема совместности таких систем является NP-полной.
Литература:
- Даниярова Э. Ю., Мясников А. Г., Ремесленников В. Н. Алгебраическая геометрия над алгебраическими системами. Новосибирск: Изд-во СО РАН, 2016.
- Ильев А. В., Ремесленников В. Н. Исследование совместности систем уравнений над графами и нахождение их общих решений // Вестн. Омск. ун-та. 2017. № 4. С. 26–32.
- Ильев А. В., Ильев В. П. Алгоритмы решения систем уравнений над различными классами конечных графов // Прикл. дискрет. математика. 2021. № 54. С. 89–102.
- Ильев А. В. Исследование систем уравнений над различными классами конечных матроидов // Сиб. электрон. мат. изв. 2022. Т. 19, № 2. С. 1094–1102.
- Никитин А. Ю., Рыбалов А. Н. О сложности проблемы разрешимости систем уравнений над конечными частичными порядками // Прикл. дискрет. математика. 2018. № 39. С. 94–98.
- Никитин А. Ю. Алгебраическая геометрия и алгоритмы в классе частично упорядоченных множеств // Вестн. Омск. ун-та. 2024. Т. 29, № 1. С. 23–32.
- Когабаев Н. Т. Об системах диофантовых уравнений над конечными конфигурациями // Сиб. мат. журн. 2023. Т. 64, № 2. С. 321–338.
- Hughes D. R., Piper F. C. Projective planes. New York, Heidelberg, Berlin: Springer-Verl., 1973.
- Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.
- Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ, 2-е изд.. М.: Вильямс, 2005.
Работа выполнена за счет гранта Российского научного фонда, проект № 23-11-00170, https://rscf.ru/project/23-11-00170.
Когабаев Нурлан Талгатович (ORCID 0000-0002-3940-0824)
- Институт математики им. С. Л. Соболева СО РАН,
пр. Академика Коптюга, 4, Новосибирск 630090 - Новосибирский государственный университет,
ул. Пирогова, 1, Новосибирск 630090
E-mail: kogabaev@math.nsc.ru
Статья поступила 14 ноября 2024 г.
После доработки — 14 ноября 2024 г.
Принята к публикации 25 апреля 2025 г.