EN
Сложность задачи о существовании сюръективного гомоморфизма на рефлексивные циклы
Опубликована: 2023 год, том 27, выпуск 4, С. 40–61
Аннотация
В работе исследуется сложность массовой задачи, где на вход подается произвольный граф, и нужно определить, существует ли сюръективный гомоморфизм из этого графа в фиксированный граф G. Мы доказываем, что если G рефлексивный цикл длины 7 и более, то задача является NP-трудной. Доказательство основано на новом подходе, который позволяет сводить решение задачи удовлетворения ограничениям к проверке выполнимости системы тождеств, а она сводится к решению сюръективной задачи удовлетворения ограничениям.
Ключевые слова: сюръективные гомоморфизмы, сложность вычислений, удовлетворение ограничениям, полиморфизмы.
BibTeX
@article{IS-Korchagin2023,
author = {Корчагин, Никита Павлович},
title = {{Сложность задачи о существовании сюръективного гомоморфизма на рефлексивные циклы}},
journal = {Интеллектуальные системы. Теория и приложения},
year = {2023},
volume = {27},
number = {4},
pages = {40--61},
}
AMSBIB
\RBibitem{IS-Korchagin2023}
\by Н.\,П.~Корчагин
\paper Сложность задачи о существовании сюръективного гомоморфизма на рефлексивные циклы
\jour Интеллектуальные системы. Теория и приложения
\yr 2023
\vol 27
\issue 4
\pages 40--61