Представлены результаты, касающиеся основной проблемы алгебраической геометрии над частично упорядоченными множествами с вычислительной точки зрения, а именно задачи разрешимости системы уравнений над частичным порядком. Задача разрешимости систем уравнений разрешима за полиномиальное время, если ориентированный граф, соответствующий частичному порядку, является приведённым интервальным орграфом, и является NP-полной, если основание ориентированного графа соответствующего частичного порядка является циклом длины не меньше 4. Получен также результат, характеризующий возможность перехода от бесконечных систем уравнений над частичным порядком к конечным системам. Алгебраические системы, обладающие указанным свойством, называются нётеровыми по уравнениям. Частично упорядоченное множество обладает свойством нётеровости по уравнениям тогда и только тогда, когда любые его верхние и нижние конусы с базой являются конечно определёнными.
Скачать электронную версию публикации
Загружен, раз: 10
- Title Критерий нётеровости по уравнениям и сложности проблемы разрешимости для систем уравнений над частично упорядоченными множествами
- Headline Критерий нётеровости по уравнениям и сложности проблемы разрешимости для систем уравнений над частично упорядоченными множествами
- Publesher
Tomsk State University
- Issue Прикладная дискретная математика 64
- Date:
- DOI 10.17223/20710410/64/1
Ключевые слова
системы уравнений, вычислительная сложность, частично упорядоченное множество, нётеровостъ по уравнениям, конусы, разрешимостьАвторы
Ссылки
Даниярова Э. Ю., Мясников А. Г., Ремесленников В. Н. Алгебраическая геометрия над алгебраическими системами. Новосибирск: Изд-во СО РАН, 2016. 243 с.
Гуров С. И. Булевы алгебры, упорядоченные множества, решетки: Определения, свойства, примеры. М.: Либроком, 2013. 221с.
Гретцер Г. Общая теория решеток. М.: Мир, 1982. 456 с.
Оре О. Теория графов. М.: Наука, 1980. 380 с.
Feder Т., Hell Р., Hunag J., and Rafiey A.Interval graphs, adjusted interval digraphs, and reflexive list homomorphism // Discr. Appl. Math. 2012. V. 160. Iss.6. P.697-707.
Feder T., Hell P., and Hunag J. List Homomorphisms and Retractions to Reflexive Digraphs. http://theory.stanford.edu/~tomas/ref.pdf. 2007. 26p.
Hell P. and Rafiey A. The Dichotomy of List Homomorphisms for Digraphs, http://arxiv.org/abs/1004.2908. 2010.
Feder T. and Hell P. List homomorphisms to reflexive graphs //j.Combinatorial Theory. 1998. V.72. No.2. P.236-250.

Критерий нётеровости по уравнениям и сложности проблемы разрешимости для систем уравнений над частично упорядоченными множествами | Прикладная дискретная математика. 2024. № 64. DOI: 10.17223/20710410/64/1
Скачать полнотекстовую версию
Загружен, раз: 141