ГлавнаяАрхивО сложности проблемы разрешимости систем уравнений над конечными частичными порядками

О сложности проблемы разрешимости систем уравнений над конечными частичными порядками | Прикладная дискретная математика. 2018. № 39. DOI: 10.17223/20710410/39/8

Классическая алгебраическая геометрия изучает множества решений алгебраических уравнений над полями вещественных и комплексных чисел. В рамках вычислительной алгебраической геометрии предложены алгоритмы (например, алгоритм Бухбергера) для решения систем полиномиальных уравнений над этими полями. Универсальная алгебраическая геометрия изучает системы уравнений над произвольными алгебраическими системами. Под уравнениями понимаются атомарные формулы языка алгебраической системы. В работе рассматривается проблема распознавания разрешимости систем уравнений над конечными частично упорядоченными множествами. Доказывается, что эта проблема является NP-полной в случае, когда проверяется существование решения, состоящего из попарно различных элементов частично упорядоченного множества.
  • Title О сложности проблемы разрешимости систем уравнений над конечными частичными порядками
  • Headline О сложности проблемы разрешимости систем уравнений над конечными частичными порядками
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 39
  • Date:
  • DOI 10.17223/20710410/39/8
Ключевые слова
частично упорядоченное множество, системы уравнений, NP-полнота, partially ordered sets, systems of equations, NP-completeness
Авторы
Ссылки
Матиясевич Ю. В. Диофантовость перечислимых множеств // Доклады Академии наук СССР. 1970. Т. 191. №2. С. 279-282.
Mayr E. W. and Meyer A. R. The complexity of the word problems for commutative semigroups and polynomial ideals // Adv. Math. 1982. V.46 (3). P.305-329.
Cook S. A. The complexity of theorem proving procedures // Proc. 3d Ann. ACM Symp. Theory of Computing. N.Y., USA, 1971. P.151-158.
Даниярова Э. Ю., Мясников А. Г., Ремесленников В. Н. Алгебраическая геометрия над алгебраическими системами. Новосибирск: СО РАН, 2016. 288с.
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 419с.
Werth T., Worlein M., Dreweke A., et al. DAG mining for code compaction / eds. L. Cao, P. S. Yu, C. Zhang, and H. Zhang. Data Mining for Business Applications. Boston, MA: Springer, 2009. P. 209-223.
Оре О. Теория графов. М.: Наука, 1980. 336 с.
О сложности проблемы разрешимости систем уравнений над конечными частичными порядками | Прикладная дискретная математика. 2018. № 39. DOI: 10.17223/20710410/39/8
О сложности проблемы разрешимости систем уравнений над конечными частичными порядками | Прикладная дискретная математика. 2018. № 39. DOI: 10.17223/20710410/39/8