КРИТЕРИЙ НЁТЕРОВОСТИ ПО УРАВНЕНИЯМ И СЛОЖНОСТИ ПРОБЛЕМЫ РАЗРЕШИМОСТИ ДЛЯ СИСТЕМ УРАВНЕНИЙ НАД ЧАСТИЧНО УПОРЯДОЧЕННЫМИ МНОЖЕСТВАМИ (2024)

Представлены результаты, касающиеся основной проблемы алгебраической геометрии над частично упорядоченными множествами с вычислительной точки зрения, а именно задачи разрешимости системы уравнений над частичным порядком. Задача разрешимости систем уравнений разрешима за полиномиальное время, если ориентированный граф, соответствующий частичному порядку, является приведённым интервальным орграфом, и является NP-полной, если основание ориентированного графа соответствующего частичного порядка является циклом длины не меньше 4. Получен также результат, характеризующий возможность перехода от бесконечных систем уравнений над частичным порядком к конечным системам. Алгебраические системы, обладающие указанным свойством, называются нётеровыми по уравнениям. Частично упорядоченное множество обладает свойством нётеровости по уравнениям тогда и только тогда, когда любые его верхние и нижние конусы с базой являются конечно определёнными.

Издание: ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА
Выпуск: № 64 (2024)
Автор(ы): НИКИТИН А.Ю., КУДЫК И.Д.
Сохранить в закладках