Аннотация:
Классическая алгебраическая геометрия изучает множества решений алгебраических уравнений над полями вещественных и комплексных чисел. В рамках вычислительной алгебраической геометрии предложены алгоритмы (например, алгоритм Бухбергера) для решения систем полиномиальных уравнений над этими полями. Универсальная алгебраическая геометрия изучает системы уравнений над произвольными алгебраическими системами. Под уравнениями понимаются атомарные формулы языка алгебраической системы. В работе рассматривается проблема распознавания разрешимости систем уравнений над конечными частично упорядоченными множествами. Доказывается, что эта проблема является NP-полной в случае, когда проверяется существование решения, состоящего из попарно различных элементов частично упорядоченного множества.
Ключевые слова:
частично упорядоченное множество, системы уравнений, NP-полнота.
Образец цитирования:
А. Ю. Никитин, А. Н. Рыбалов, “О сложности проблемы разрешимости систем уравнений над конечными частичными порядками”, ПДМ, 2018, № 39, 94–98
\RBibitem{NikRyb18}
\by А.~Ю.~Никитин, А.~Н.~Рыбалов
\paper О сложности проблемы разрешимости систем уравнений над конечными частичными порядками
\jour ПДМ
\yr 2018
\issue 39
\pages 94--98
\mathnet{http://mi.mathnet.ru/pdm614}
\crossref{https://doi.org/10.17223/20710410/39/8}
\elib{https://elibrary.ru/item.asp?id=32724378}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdm614
https://www.mathnet.ru/rus/pdm/y2018/i1/p94
Эта публикация цитируется в следующих 6 статьяx:
А. В. Ильев, “Аксиоматизируемость и разрешимость универсальных теорий наследственных классов моделей конечных и бесконечных языков”, ПДМ, 2024, № 66, 14–29
Н. Т. Когабаев, “О системах диофантовых уравнений над конечными конфигурациями”, Сиб. матем. журн., 64:2 (2023), 321–338; N. T. Kogabaev, “Systems of diophantine equations over finite configurations”, Siberian Math. J., 64:2 (2023), 325–337
А. В. Ильев, В. П. Ильев, “Алгоритмы решения систем уравнений над различными классами конечных графов”, ПДМ, 2021, № 53, 89–102
А. В. Селиверстов, “Симметричные матрицы, элементами которых служат линейные функции”, Ж. вычисл. матем. и матем. физ., 60:1 (2020), 109–115; A. V. Seliverstov, “Symmetric matrices whose entries are linear functions”, Comput. Math. Math. Phys., 60:1 (2020), 102–108
А. Ю. Никитин, “Разрешимость ограниченных теорий класса частичных порядков”, ПДМ, 2019, № 45, 6–12
A Yu Nikitin, “On radicals and coordinate partial orders”, J. Phys.: Conf. Ser., 1260:2 (2019), 022004
Цитирование в формате AMSBIB
Обратная связь: