Сложность задачи проверки тождеств в конечных полугруппах

• Автор: Гольдберг, Светлана Викторовна
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Екатеринбург
• Количество страниц: 74 с. : ил.

Содержание
Введение
0.1 Алгебра, алгоритмы и сложность
0.2 Предварительные сведения
0.3 Проблема проверки тождеств в алгебрах
0.4 Задача проверки тождеств для конечных полугрупп
0.5 Постановка задач
0.6 Результаты диссертации
0.7 Апробация результатов
0.8 Список обозначений
1 Пример 0-простой полугруппы с соР-полной задачей проверки тождеств
1.1 Некоторые свойства полугруппы М
1.2 Необходимые сведения о задачах на графах
1.3 Минимальность М. среди сложных 0-простых полугрупп
1.4 Графовые конструкции в задаче СЬеск-1с1(Л4)
1.5 Условия выполнения тождества в полугруппе М
1.6 Взаимосвязь задач СЬеск-1с)(Л4) и ВЕуеп-Нот(Дег;)
1.7 Сведение задачи ВЕуеп-Нот(Нвх) к задаче СЬеск-1с1(Л4)
1.8 Взаимосвязь задачи о ретракции графов,
задачи Еуеп-Нот и задачи ВЕуеп-Нот
1.9 Представление полугруппы М с помощью преобразований 3-
элементного множества
2 Сведение задачи проверки тождеств в полугруппах к задаче проверки тождеств в группах
3 Сложность проверки тождеств в полной полугруппе преобразований
4 Сложность проверки тождеств в полугруппе преобразований ранга
4.1 Легкость проверки тождеств в Т2(п) при пф
4.2 Сложность проверки тождеств в Тг(3)
Список литературы

Введение
0.1 Алгебра, алгоритмы и сложность
Сама наука алгебра в свое время возникла как алгоритмическая дисциплина, призванная упорядочить и объединить методы решения возникавших задач. И в современном мире приложения алгебры как в других областях математики, так и за пределами математики чаще всего связаны с алгоритмическими аспектами. Теме алгоритмических проблем в алгебре посвящено на сегодняшний день большое число публикаций. Важные работы на эту тему были выполнены в научной школе Л.Н. Шеврина: см., папример, обзор О.Г. Харлампович и М.В. Сапира по алгоритмическим проблемам в многообразиях [27] и диссертацию В.Ю. Попова [8].
Если до недавнего времени конечной точкой исследования алгоритмических задач было установление их разрешимости или неразрешимости, то возникшая в 1970-х годах формализация сложности алгоритмов открыла большой горизонт для дальнейшего изучения алгоритмически разрешимых задач. Теория вычислительной сложности началась с работ Кука [18], Левина [5] и Карпа [26] и сразу же набрала грапдиозную скорость своего развития, благодаря как открывшимся теоретическим перспективам, так и существенной потребности практиков в исследовании реальных возможностей алгоритмов. Общее представление о теории вычислительной сложности можно получить из классических учебников [2] и [36].
Применительно к обсуждавшейся области обнаружилось, что многие базовые алгоритмические задачи алгебры, разрешимость которых давно известна и/или очевидна, приводят к интересным и зачастую весьма трудным проблемам, если задаться вопросом о вычислительной сложности соответствующих алгоритмов. С одной стороны, интересен непосредственно слож-ностный анализ алгебраических алгоритмов. С другой стороны, если решается задача, в которой алгебра или класс алгебр выступают в качестве входного параметра, то интересно изучить взаимосвязь сложности соответствующего алгоритма и строения алгебры (класса алгебр) и тем самым, возможно, классифицировать алгебры по сложности рассматриваемой задачи.
В качестве примера упомянем следующую задачу Var-Memb (необходимые определения можно найти в §0.2): для двух конечных алгебр А и В одинаковой сигнатуры определить, удовлетворяет ли алгебра А всем тооюде-ствам алгебры В. (Обозначение Var-Memb произведено от ‘Variety membership”, поскольку в терминах теории многообразий речь идет о распознавании принадлежности алгебры А многообразию, порожденному алгеброй В). Понятно значение задачи Var-Memb для современной универсальной алгебры, в которой, как хорошо известно, классификация алгебр с помощью тождеств

занимает одно из центральных мест. Алгоритмическая разрешимость задачи /аг-МетЬ легко выводится из НБР-теоремы Тарского и отмечалась еще в пионерской работе Калицкого [25]. Исследование же вычислительной сложности этой задачи началось сравнительно недавно и принесло довольно неожиданные результаты. Верхнюю оценку привели Бергман и Слуцки [13], установившие, что задача /аг-МетЬ принадлежит классу 2-ЕХРТ1МЕ (класс задач, разрешимых за дважды экспоненциальное время). Эта оценка сперва представлялась сильно завышенной, но затем Секели [46] показал, что обсуждаемая задача N Р-трудна, а на конференции в Сегеде в 2007 Козик анонсировал (см. [32]) пример алгебры с 2-ЕХРТ1МЕ-полной задачей /аг-МетЬ, тем самым доказав точность оценки 2-ЕХРТ1МЕ.
Задача, рассматриваемая в настоящей работе, в определенном смысле еще более фундаментальна, чем задача /аг-МетЬ. В последней спрашивается, удовлетворяет ли алгебра А каждому из (бесконечно многих) тождеств алгебры В, в то время как здесь мы локализуем ситуацию, спрашивая, выполняется ли в фиксированной конечной алгебре А одно данное тождество. Соответствующую задачу будем называть задачей проверки тождеств в алгебре А и обозначать через СЬеск-1б(Д).
Указанная задача интересна для компьютерных наук, например, в ее связи с теорией спецификаций. Под формальными алгебраическими специфи-кациями понимают выражения, записанные на языке, описывающем программные системы, их свойства и поведение при различных входных данных, без учета ограничений, которые могут возникнуть в результате конкретной реализации данной программной системы. Подобная абстракция, не зависящая от конкретных решений реализации, делает формальные спецификации исключительно полезными при разработке программных систем: спецификации играют роль посредника между пользователями, разработчиками, тестировщиками и писателями технической документации. Формальные спецификации успешно применяются в разработке сложных программных систем (см., например, [49]).
Математически, формальные спецификации основаны на алгебраических понятиях - идеях и методах универсальной алгебры. Взаимосвязь между реализацией программной системы и ее формальной спецификацией соответствует, если говорить в алгебраических терминах, взаимосвязи между алгеброй и множеством тождеств, в этой алгебре выполненных. Таким образом, изучение вычислительной сложности проверки тождеств в алгебрах важно для исследований в теории формальных спецификаций, в том числе для построения эффективных систем проверки моделей на соответствие заявленным требованиям.
Дадим теперь строгое определение. Под задачей проверки тождеств в

это объединение ребер в смысле мультимножеств, т. е. состоит из множества всех ребер Ер и Еч в качестве носителя, и при этом каждое ребро получает кратность, равную сумме его кратностей в мультиграфах Ср и Сч.
Пример 1.3. Пусть дано слово у = х12х2х1х3ххх2- Слово р возьмем из примера 1.2. Тогда:
&2 Аз &4 О5 Ч А 2 A3 А4 А5
Ь f>2 63 64 65 61 62 3 4 дг,
а 1 Я2 ЙЗ Й4 Й5
Рис. 5:
Далее мы приведем условия, эквивалентные условиям 3, 4.
Условие 3'. Степень каждой вершины графа UG четна.
Доказательство. Для начала заметим, что условие 3 можно переформулировать следующим образом: для каждой вершины графа Gp аналогичная вершина (отвечающая той же букве алфавита и в той же доле) в графе Gq имеет степень такой же четности. Отсюда и из определения мультиграфа UG немедленно следует эквивалентность условий 3 и 3'.
Условие 4'. Для произвольного двудольного гомоморфизма ip : UG —> Hex каждое ребро (А, г) £ Hex имеет четный по мощности прообраз, т. е.
|-1(А,г)| = 0 mod 2.
Доказательство. Прежде всего напомним, что мультиграфы Gp, Gq и UG совпадают как обыкновенные графы (если кратностям всех ребер приписать единицу). Следовательно, гомоморфизм ip можно рассматривать как гомоморфизм графов Gp и G,r При этом, замечания 1.3 и 1.4 устанавливают взаимнооднозначное соответствие между произвольными двудольными