Алгебраические методы в исследовании комбинаторных задач

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

Оглавление
Введение

В.1. Задача СЭР

В.2. Обзор предшествующих исследований

В.З. Цели работы

В.4. Основные проблемы

В.5. Основные результаты

В.6. Основные методы

В.7. Структура диссертации

В.8. Апробация и публикации

Глава 0. Базисные понятия и факты

§1. Задача СЭР
1.1. Основные понятия теории сложности
1.2. Эквивалентные определения задачи СЭР
1.3. Задачи о подсчете решений
1.4. Локальные метод!,т
§2. Алгебры и операции
2.1. Клоны операций и отношений
2.2. От множеств отношений к клонам отношений и далее к клонам функций
2.3. Теория ручных конгруэнций
2.4. Свойства мальцевских алгебр
2.5. Простые и строго простые идемпотентные алгебр
Глава 1. Задачи распознавания
§3. Алгебраический подход в задачах СБР
3.1. От клонов функций к алгебрам и далее к многообразиям алгебр
3.2. Многосортная задача СЭР
3.3. Три уровня полиномиальности
§4. МР-иолнота и гипотеза о дихотомии
4.1. ИР-полные алгебры и результаты о дихотомии
4.2. Необходимое условие полиномиальности на языке теории ручных конгруэнций
4.3. Распознавание полиномиальных задач
§5. Полиномиальные алгебры: 2-полурешетки

Оглавление З
5.1. Вспомогательные наблюдения
5.2. Простые 2-полурешетки
5.3. Общий случай
§6. Полиномиальные алгебры: мальцевские алгебры
6.1. Строение подпрямых произведении алгебр с мальцевской операцией
6.2. Задачи СЭР с мальцевским полиморфизмом
6.3. Подпрограммы и комментарии
6.4. Два типа алгоритмов
§7. Результаты о дихотомии: строго простіло алгебры
§8. Результаты о дихотомии: З-элементные алгебры
8.1. Полиномиальные множества отношений на 3-элементном множестве
8.2. Алгоритмы для задач СЭР на З-элемептном множестве
8.3. Доказательство теоремы
8.4. Практическое руководство к решению задач СЭР на 3-элементном множестве135
§9. Результаты о дихотомии: копссриативные алгебры
9.1. Схема доказательства
9.2. Структура отношений из консерпатипных языков
9.3. Двусвязные отношения
9.4. Связность, прямоуголытсть и разложения
9.5. Я/Ь-связные отношения
9.6. Алгоритм
§10. Идемпотентные алгебры и реберно-окрашенные графы
10.1. Три типа ребер
10.2. Красные ребра
§11. Алгебры конечной ширины
11.1. Ограниченная ширина и избегание синих ребер
11.2. З-элементные алгебры ограниченной ширины
11.3. Консервативные алгебры ограниченной ширины
11.4. Достаточные условия конечности ширины
§12. Результаты о дихотомии: алгебры с минимальным клоном термальных операций
Глава 2. Задачи о подсчете числа решений
§13. Алгебраический подход к задачам о подсчете числа решений
13.1. От множеств отношений к клонам отношений п далее к клонам функций
13.2. От клонов к алгебрам и многообразиям
13.3. Трудные задачи о подсчете решений и мальцевские операции
§14. Сингулярные алгебры и многообразия
14.1. Взвешенная задача СЭР
14.2. Теорема о #Р-трудности
14.3. От чисел к полиномам
14.4. Расширение множества отношений
14.5. Перестановочные отношения эквивалентности

Оглавление

14.6. Удаление нулей
14.7. Упорядочение единиц
14.8. Матрицы, содержащие не менее двух 1-клеток
14.9. Матрицы с одной клеткой
§15. Дихотомия для задач о подсчете числа решений
15.1. Решетки конгруэнций мальцевских алгебр
15.2. Дополнительные свойства отношений, инвариантных относительно маль-цевской операции
15.3. Необходимые условия полиномиальной разрешимости
15.4. Алгоритмы
Литература
Предметный указатель
Глава 0. Базисные понятия и факты

Предложение 2.6 (Джевонс,[139[). Пусть Г — множество отношений па конечном множестве А. Следующие утверждения эквивалентны:
CSP(r) имеет сильную ширину к;
Г инвариантно относительно некоторой (к 1)-местной функции почти единогласия.
2.3 Теория ручных конгруэнций
В теории ручных конгруэнций каждой паре конгруэнций а -< (5 (т.е. такой, что /3 покрывает а) конечной алгебры А присваивается один из 5 типов. Пусть основное множество алгебры А обозначается через А. Множество U С А называется (а,р)-минималъным множеством, если оно минимально относительно включения среди подмножеств из А, которые могут быть представлены в виде ДА), где } — унарный полином А такой, что /(/3) 2 а. Пусть, далее, Т = BnU для некоторого /3-класса В такого, что Т2 % а. Тогда Т называется (а,р)-следом, а алгебра Т = А, = (Т; F), где F = {/J | / — полином А, сохраняющий Г}, называется индуцированной алгеброй. Алгебра Т/а|г полиномиально эквивалентна алгебре одного из следующих пяти типов, которые отражают особенности локального строения А:
1 конечное G-множество, т.е. множество с действующей на нем группой;
2 конечное векторное пространство;
3 двухэлементная булева алгебра;
4 двухэлементная решетка;
5 двухэлементная полурешетка.
Тип индуцированной алгебры Т/а|г зависит только от конгруэнций а,/3 и не зависит от выбора следа. Таким образом, этот тіш может быть присвоен паре (простому интервалу) (<*.£) Тип простого интервала обозначается через typ(a,/3). Далее, typ(A) = {typ(a,/3) | а, /З Є Con(A), а -< /3}; п для класса конечных алгебр 21 положим typ(2l) = UAsatyP)- Если для конечной алгебры А [класса конечных алгебр 21] имеет место і £ typ(A) [і g typ(2t)j, то мы говорим, что А [соответственно 21] избегает тип і.
2.4 Свойства мальцевских алгебр
Простые интервалы решетки конгруэнций малъцсвской алгебры могут иметь лишь типы 2 и 3. Пусть А — мальцевская алгебра и а -< /3 — ее конгруэнции. Класс конгруэнции а, содержащий элемент а, мы будем обозначать через аа. Операция алгебры А/й, соответствующая операции / алгебры А, будет обозначаться через /“. Пусть также (5/а обозначает конгруэнцию алгебры А/а, определенную следующим образом ([130, 96]): (аа,Ьа) Є (3/а тогда и только тогда, когда [а,Ь) Є р. Следующее предложение отчасти следует из результатов [130, 96) и теоремы 8.5 [131], а отчасти является фольклором.
Предложение 2.7. Пусть А — мальцевская алгебра, d — ее малъцевский терм и а -< /3 — ее конгруэнции.
(1) Минимальные множества малъцевких алгебр являются объединением следов.