Введение
Глава 0. Базисные понятия и факты 21
1. Задача CSP 21
1.1. Основные понятия теории сложности 21
1.2. Эквивалентные определения задачи CSP 22
1.3. Задачи о подсчете решений 26
1.4. Локальные методы 27
2. Алгебры и операции 31
2.1. Клоны операций и отношений 31
2.2. От множеств отношений к клонам отношений и далее к клонам функций . 32
2.3. Теория ручных конгруэнции 35
2.4. Свойства мальцевских алгебр 35
2.5. Простые и строго простые идемпотентные алгебр 36
Глава 1. Задачи распознавания 38
3. Алгебраический подход в задачах CSP 38
3.1. От клонов функций к алгебрам и далее к многообразиям алгебр 38
3.2. Многосортная задача CSP 42
3.3. Три уровня полиномиальности 52
4. NP-полнота и гипотеза о дихотомии 53
4.1. NP-полные алгебры и результаты о дихотомии 53
4.2. Необходимое условие полиномиальности на языке теории ручных конгруэнции 54
4.3. Распознавание полиномиальных задач 55
5. Полиномиальные алгебры: 2-полурешетки 64
5.1. Вспомогательные наблюдения 64
5.2. Простые 2-полурешетки 65
5.3. Общий случай 70
6. Полиномиальные алгебры: мальцевские алгебры 72
6.1. Строение подпрямых произведений алгебр с мальцевской операцией 73
6.2. Задачи CSP с мальцевским полиморфизмом 80
6.3. Подпрограммы и комментарии 86
6.4. Два типа алгоритмов 97
7. Результаты о дихотомии: строго простые алгебры 98
8. Результаты о дихотомии: 3-элементные алгебры 99
8.1. Полиномиальные множества отношений на 3-элементном множестве 100
8.2. Алгоритмы для задач CSP на 3-элемептпом множестве 102
8.3. Доказательство теоремы 8.2 107
8.4. Практическое руководство к решению задач CSP на 3-элементном множестве 135 9. Результаты о дихотомии: консервативные алгебры 137
9.1. Схема доказательства 138
9.2. Структура отношений из консервативных языков 140
9.3. Двусвязные отношения 150
9.4. Связность, прямоуголыюсть и разложения 166
9.5. R/b-связные отношения 179
9.6. Алгоритм 199
10. Идемпотентные алгебры и реберно-окрашенные графы 208
10.1. Три типа ребер 208
10.2. Красные ребра 223
11. Алгебры конечной ширины 226
11.1. Ограниченная ширина и избегание синих ребер 226
11.2. 3-элементные алгебры ограниченной ширины 228
11.3. Консервативные алгебры ограниченной ширины 231
11.4. Достаточные условия конечности ширины 231
12. Результаты о дихотомии: алгебры с минимальным клоном термаль
ных операций 232
Глава 2. Задачи о подсчете числа решений 235
13. Алгебраический подход к задачам о подсчете числа решений 235
13.1. От множеств отношений к клонам отношений и далее к клонам функций 235
13.2. От клонов к алгебрам и многообразиям 238
13.3. Трудные задачи о подсчете решений и мальцевские операции 242
14. Сингулярные алгебры и многообразия 248
14.1. Взвешенная задача CSP 249
14.2. Теорема о #Р-трудности 254
14.3. От чисел к полиномам 256
14.4. Расширение множества отношений 261
14.5. Перестановочные отношения эквивалентности 268
14.6. Удаление нулей 268
14.7. Упорядочение единиц 270
14.8. Матрицы, содержащие не менее двух 1-клегок 275
14.9. Матрицы с одной клеткой 281
15. Дихотомия для задач о подсчете числа решений 291
15.1. Решетки конгруэнции мальцевских алгебр 291
15.2. Дополнительные свойства отношений, инвариантных относительно маль-цевской операции 293
15.3. Необходимые условия полиномиальной разрешимости 294
15.4. Алгоритмы 297
Литература 304
Предметный указатель 319
