Эта публикация цитируется в 2 статьях

Часть 2. Специальные вопросы теории интеллектуальных систем

Сложность задачи о существовании сюръективного гомоморфизма на рефлексивные циклы

Н. П. Корчагин

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

Аннотация: В работе исследуется сложность массовой задачи, где на вход подается произвольный граф, и нужно определить, существует ли сюръективный гомоморфизм из этого графа в фиксированный граф $G$. Мы доказываем, что если $G$ рефлексивный цикл длины $7$ и более, то задача является $NP$-трудной. Доказательство основано на новом подходе, который позволяет сводить решение задачи удовлетворения ограничениям к проверке выполнимости системы тождеств, а она сводится к решению сюръективной задачи удовлетворения ограничениям.

Ключевые слова: сюръективные гомоморфизмы, сложность вычислений, удовлетворение ограничениям, полиморфизмы