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

doi:10.17223/20710410/39/8

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
О сложности проблемы разрешимости систем уравнений над конечными частичными порядками	103 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/39/8

#частично упорядоченные множества

#системы уравнений

#NP-полнота

Title: О сложности проблемы разрешимости систем уравнений над конечными частичными порядками
Title: On complexity of the satisfiability problem of systems over finite posets
Creator: Никитин, Алексей Юрьевич
|
Рыбалов, Александр Николаевич
Date: 2018
DOI: 10.17223/20710410/39/8
Description: Классическая алгебраическая геометрия изучает множества решений алгебраических уравнений над полями вещественных и комплексных чисел. В рамках вычислительной алгебраической геометрии предложены алгоритмы (например, алгоритм Бухбергера) для решения систем полиномиальных уравнений над этими полями. Универсальная алгебраическая геометрия изучает системы уравнений над произвольными алгебраическими системами. Под уравнениями понимаются атомарные формулы языка алгебраической системы. В работе рассматривается проблема распознавания разрешимости систем уравнений над конечными частично упорядоченными множествами. Доказывается, что эта проблема является NP-полной в случае, когда проверяется существование решения, состоящего из попарно различных элементов частично упорядоченного множества.

Relationships: Show Relationship Browser for this Object
collection(s): Журналы ТГУ
Identifier: смотреть в электронном каталоге НБ ТГУ
Type: статьи в журналах
Source: Прикладная дискретная математика. 2018. № 39. С. 94-98
Language: rus

Created: 22-03-2018

1378 Visitors

1168 Hits

221 Downloads

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