Н. Т. Когабаев, “NP-полнота проблемы совместности систем диофантовых уравнений над конечными конфигурациями”, Сиб. матем. журн., 2025, том 66, номер 3,страницы 450

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

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

^a Институт математики им. С. Л. Соболева СО РАН, пр. Академика Коптюга, 4, Новосибирск 630090
^b Новосибирский государственный университет, ул. Пирогова, 1, Новосибирск 630090

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

Ключевые слова: конфигурация, инцидентность, система уравнений, недетерминированная машина Тьюринга, NP-полная проблема.

УДК: 510.522+514.146

Статья поступила: 14.11.2024
Окончательный вариант: 14.11.2024
Принята к печати: 25.04.2025

DOI: 10.33048/smzh.2025.66.310