Сложность проблемы совместности систем диофантовых уравнений над конечными двудольными графами Научная публикация
| Журнал |
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports)
, E-ISSN: 1813-3304 |
||||
|---|---|---|---|---|---|
| Вых. Данные | Год: 2026, Том: 23, Номер: 1, Страницы: 266-288 Страниц : 23 DOI: 10.33048/semi.2026.23.017 | ||||
| Ключевые слова | двудольный граф, система уравнений, недетерминированная машина Тьюринга, NP-полная проблема | ||||
| Авторы |
|
||||
| Организации |
|
Информация о финансировании (1)
| 1 | Министерство науки и высшего образования РФ | FWNF-2026-0032 |
Реферат:
Изучаются конечные системы диофантовых уравнений над конечными двудольными графами. В 2021 году А.В.Ильевым и В.П.Ильевым была предложена детерминированная полиномиальная процедура для проверки совместности таких систем. Мы строим контрпример, показывающий, что предложенная ими процедура работает некорректно, и доказываем, что проблема совместности таких систем на самом деле является NP-полной.
Библиографическая ссылка:
Кобзев Ф.Д.
, Когабаев Н.Т.
Сложность проблемы совместности систем диофантовых уравнений над конечными двудольными графами
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2026. Т.23. №1. С.266-288. DOI: 10.33048/semi.2026.23.017 Scopus
Сложность проблемы совместности систем диофантовых уравнений над конечными двудольными графами
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2026. Т.23. №1. С.266-288. DOI: 10.33048/semi.2026.23.017 Scopus
Даты:
| Поступила в редакцию: | 19 июн. 2025 г. |
| Принята к публикации: | 12 дек. 2025 г. |
| Опубликована в печати: | 31 мар. 2026 г. |
| Опубликована online: | 31 мар. 2026 г. |
Идентификаторы БД:
| ≡ Scopus: | 2-s2.0-105035093950 |