Сложность проблемы совместности систем диофантовых уравнений над конечными двудольными графами Full article
| Journal |
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports)
, E-ISSN: 1813-3304 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2026, Volume: 23, Number: 1, Pages: 266-288 Pages count : 23 DOI: 10.33048/semi.2026.23.017 | ||||
| Tags | двудольный граф, система уравнений, недетерминированная машина Тьюринга, NP-полная проблема | ||||
| Authors |
|
||||
| Affiliations |
|
Funding (1)
| 1 | Министерство науки и высшего образования РФ | FWNF-2026-0032 |
Abstract:
Изучаются конечные системы диофантовых уравнений над конечными двудольными графами. В 2021 году А.В.Ильевым и В.П.Ильевым была предложена детерминированная полиномиальная процедура для проверки совместности таких систем. Мы строим контрпример, показывающий, что предложенная ими процедура работает некорректно, и доказываем, что проблема совместности таких систем на самом деле является NP-полной.
Cite:
Кобзев Ф.Д.
, Когабаев Н.Т.
Сложность проблемы совместности систем диофантовых уравнений над конечными двудольными графами
Сибирские электронные математические известия (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
Dates:
| Submitted: | Jun 19, 2025 |
| Accepted: | Dec 12, 2025 |
| Published print: | Mar 31, 2026 |
| Published online: | Mar 31, 2026 |
Identifiers:
| ≡ Scopus: | 2-s2.0-105035093950 |