Оглавление
Введение
В. 1. Задача
В.2. Обзор предшествующих исследований
В.З. Пели работы
В.4. Основные проблемы.
В.5. Основные результаты.
В.б. Основные методы.
В.7. Структура диссертации.
В.8. Апробация и публикации
Глава 0. Базисные понятия и факты
1. Задача .
1.1. Основные понятия теории сложности.
1.2. Эквивалентные определения задачи
1.3. Задачи о подсчете спеиий.
1.4. Локальные метода
2. Алгебры и операции
2.1. Клоны операций и отношений
2.2. От множссгв отношений к клонам отношений и далее к клонам функций . .
2.3. Теория ручных конгруэнций.
2.4. Свойства мальцсвскнх алгебр.
2.5. Простые и строго простые идемпотеитные алгебр. 3
Глана 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.1. Строение подпрямых произведении алгебр с мальцевской операцией
6.2. Задачи СЭР с мальцевским полиморфизмом.
6.3. Подпрограммы и комментарии.
6.4. Два типа алгоритмов .
7. Результаты о дихотомии строго простые алгебры.
8. Результаты о дихотомии Зэлемеитные алгебры.
8.1. Полиномиальные множества отношений на 3элсментпом множестве
8.2. Алгоритмы для задач С5Р на Зэлемеитиом множестве .
8.3. Доказательство теоремы 8.2
8.4. Практическое руководство к решению задач СЭР ка 3элементном множестве
9. Результаты о дихотомии консервативные алгебры.
9.1. Схема доказательства.
9.2. Структура отношений из консервативных языков.
9.3. Двусвязные отношения
9.4. Связность, прямоуголыюсть и разложения.
9.5. НЬсвязные отношения
9.6. Алгоритм.
. Идемпотентные алгебры и реберноокрашенные графы
.1. Три типа ребер
.2. Красные ребра.
. Алгебры конечной ширины.
.1. Ограниченная ширина и избегание синих ребер.
.2. 3элементные алгебры ограниченной ширины
.3. Консервативные алгебры ограниченной ширины
.4. Достаточные условия конечности ширины.
. Результаты о дихотомии алгебры с минимальным клоном термальных операций . . .
Глава 2. Задачи о подсчете числа решений
. Алгебраический подход к задачам о подсчете числа решений
.1. От множеств отношений к клонам отношений и далее к клонам функций .
.2. От клонов к алгебрам и многообразиям
.3. Трудные задачи о подсчете решений и мальцевские операции .
. Сингулярные алгебры и многообразия .
.1. Взвешенная задача СЯР2
.2. Теорема о Ртрудности
.3. От чисел к полиномам.
.4. Расширение множества отношений
.5. Перестановочные отношения эквивалентности
Оглавление
.6. Удаление нулей .
.7. Упорядочение единиц.
.8. Матрицы, содержащие не менее двух 1клеток
.9. Матрицы с одной клеткой.
. Дихотомия для задач о подсчете числа решений.
.1. Решетки конгруэнций мальцсвских алгебр
.2. Дополнительные свойства отношений, инвариантных относительно мальцевской операции
.3. Необходимые условия полиномиальной разрешимости.
.4. Алгоритмы.
Литература
- Київ+380960830922