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

Представлены результаты, касающиеся основной проблемы алгебраической геометрии над частично упорядоченными множествами с вычислительной точки зрения, а именно задачи разрешимости системы уравнений над частичным порядком. Задача разрешимости систем уравнений разрешима за полиномиальное время, если ориентированный граф, соответствующий частичному порядку, является приведённым интервальным орграфом, и является NP-полной, если основание ориентированного графа соответствующего частичного порядка является циклом длины не меньше 4. Получен также результат, характеризующий возможность перехода от бесконечных систем уравнений над частичным порядком к конечным системам. Алгебраические системы, обладающие указанным свойством, называются нётеровыми по уравнениям. Частично упорядоченное множество обладает свойством нётеровости по уравнениям тогда и только тогда, когда любые его верхние и нижние конусы с базой являются конечно определёнными.
  • Title Критерий нётеровости по уравнениям и сложности проблемы разрешимости для систем уравнений над частично упорядоченными множествами
  • Headline Критерий нётеровости по уравнениям и сложности проблемы разрешимости для систем уравнений над частично упорядоченными множествами
  • Publesher Tomask State UniversityTomsk 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
Критерий нётеровости по уравнениям и сложности проблемы разрешимости для систем уравнений над частично упорядоченными множествами | Прикладная дискретная математика. 2024. № 64. DOI: 10.17223/20710410/64/1