RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



ПДМ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


ПДМ, 2018, номер 39, страницы 94–98 (Mi pdm614)  

Эта публикация цитируется в 1 научной статье (всего в 1 статье)

Математические основы информатики и программирования

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

А. Ю. Никитин, А. Н. Рыбалов

Омский государственный технический университет, г. Омск, Россия

Аннотация: Классическая алгебраическая геометрия изучает множества решений алгебраических уравнений над полями вещественных и комплексных чисел. В рамках вычислительной алгебраической геометрии предложены алгоритмы (например, алгоритм Бухбергера) для решения систем полиномиальных уравнений над этими полями. Универсальная алгебраическая геометрия изучает системы уравнений над произвольными алгебраическими системами. Под уравнениями понимаются атомарные формулы языка алгебраической системы. В работе рассматривается проблема распознавания разрешимости систем уравнений над конечными частично упорядоченными множествами. Доказывается, что эта проблема является NP-полной в случае, когда проверяется существование решения, состоящего из попарно различных элементов частично упорядоченного множества.

Ключевые слова: частично упорядоченное множество, системы уравнений, NP-полнота.

Финансовая поддержка Номер гранта
Российский научный фонд 17-11-01117
Работа поддержана грантом РНФ № 17-11-01117.


DOI: https://doi.org/10.17223/20710410/39/8

Полный текст: PDF файл (611 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 510.52

Образец цитирования: А. Ю. Никитин, А. Н. Рыбалов, “О сложности проблемы разрешимости систем уравнений над конечными частичными порядками”, ПДМ, 2018, № 39, 94–98

Цитирование в формате AMSBIB
\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}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/pdm614
  • http://mi.mathnet.ru/rus/pdm/y2018/i1/p94

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. А. Ю. Никитин, “Разрешимость ограниченных теорий класса частичных порядков”, ПДМ, 2019, № 45, 6–12  mathnet  crossref
  • Прикладная дискретная математика
    Просмотров:
    Эта страница:96
    Полный текст:28
    Литература:8
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020