Содержание к диссертации
Введение
Глава 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
- Основные понятия теории сложности
- Свойства мальцевских алгебр
- От клонов функций к алгебрам и далее к многообразиям алгебр
- От множеств отношений к клонам отношений и далее к клонам функций
Введение к работе
В.1 Задача CSP
Количество и многообразие комбинаторных алгоритмов, постоянно возникающих в теоретической информатике и ее приложениях, вызывают естественное стремление систематизировать и унифицировать этот массив, разработать универсальные алгоритмы, не зависящие от частных особенностей той или иной задачи. Один из возможных путей сделать это — комбинаторная задача CSP1. В задаче CSP требуется выяснить, выполнима ли в данной модели диофантова формула, т.е. экзистенциальная формула первой ступени, бескванторная часть которой является конъюнкцией атомарных формул2. В другой, эквивалентной, формулировке требуется определить, существует ли гомоморфизм между двумя конечными моделями. Хотя эта задача является лишь одной из многих известных комбинаторных задач, в последнее десятилетие стало ясно, что она занимает особое место в теоретической информатике.
Некоторые частные случаи задачи CSP рассматривались задолго до появления понятия общей задачи CSP. Например, задача Выполнимость, в которой требуется выяснить, выполнима ли формула логики высказываний в конъюнктивной нормальной форме, естестве-ным образом возникает во многих разделах теоретической информатики и активно изучалась [41, 104]. Общая задача CSP была сформулирована Монтанари в 1974 году [184], который использовал ее для моделирования пространственных взаимосвязей между объектами. Началом систематического изучения задачи CSP можно считать работу Шефера [203] 1978 года. В этой работе Шефер дал полный анализ задачи Выполнимость с точки зрения вычислительной сложности.
После работы Шефера появились сотни статей и несколько монографий, посвященных различным аспектам задачи CSP, см., например, [40, 48, G4, 92, 102, 110, 142, 143, 163, 164, 175, 176, 177, 205, 212]. Столь пристальное внимание к этой задаче вызвано тем, что она рассматривается как модель, в терминах которой может быть выражена практически любая комбинаторная задача. Выразимость одной комбинаторной задачи в терминах другой — явление в информатике вполне рядовое (см. соответствующие обсуждения и многочисленные примеры в книге [104]). Однако в большинстве случаев соответствующие представления весьма громоздки и искусственны. Преимущество задачи CSP состоит как раз в том, что большинство комбинаторных задач может быть выражено в терминах CSP естественно и просто. Задача CSP применяется во многих областях теоретической информатики, включая теорию реляционных
От английского "Constraint Satisfaction Problem"; в немногочисленных русскоязычных работах по этой проблематике встречается также название "Обобщенная выполнимость". Такие формулы называются также примитивно позитивпылш.
Введение
баз данных [154, 220], временную и пространственную логику [205], распознавание зрительных образов [184], автоматическое доказательство теорем [61], техническое проектирование [186], анализ языков программирования [185] и естественных языков [5], биоинформатику [161].
Представление на языке CSP часто позволяет избежать разработки специфического алгоритма для конкретной комбинаторной задачи. Вместо этого достаточно записать ее в форме CSP, а затем воспользоваться одним из известных алгоритмов. В последние годы возникают универсальные решатели комбинаторных задач, входом для которых служит описание комбинаторной задачи в терминах CSP. Развитие универсальных решателей этого типа и языков представления задач в CSP-форме признано ACM (Association for Computing Machinery) одним из стратегических направлений в развитии теоретической информатики. Таким образом, основная цель в исследовании CSP — найти методы решения этой задачи, которые могут быть использованы на практике.
К настоящему времени сложилось три основных направления в изучении задачи CSP.
Создание универсальных алгоритмов, решающих большинство задач CSP за приемлемое время.
Выявление подзадач задачи CSP, которые могут быть решены эффективно.
Исследование комбинаторных задач из различных областей математики в контексте задачи CSP.
Опишем основные черты этих направлений.
Первое направление состоит в разработке алгоритмов, которые, вообще говоря, сверхполиномиальны, но на практике в подавляющем большинстве случаев завершают работу за приемлемое время [33, 42, 57, 62, 64, 65, 102, 108, 156, 163, 174, 195, 218]. Чаще всего такие алгоритмы используют предварительное исследование задачи с целью выбора того или иного метода решения, а также всевозможные эвристики, позволяющие угадать решение или существенно упростить задачу. Обзор работ в данном направлении можно найти в монографиях [58, 60, 212].
Вопросы, рассматриваемые в данной диссертации, относятся в основном ко второму из перечисленных направлений. Рассмотрим поэтому его более детально.
Одной из наиболее существенных характеристик комбинаторных задач является их вычислительная сложность. Сложность задачи принято оценивать, указывая ее принадлежность к тому или иному классу сложности. Важнейшими классами сложности являются следующие: NL — класс задач, решаемых недетерминированной машиной Тьюринга с логарифмической памятью; Р — класс задач, решаемых детерминированной машиной Тьюринга за полиноми-«ільное время; NP — класс задач, решаемых недетерминированной машиной Тьюринга за полиномиальное время; PSPACE — класс задач, решаемых детерминированной машиной Тьюринга с полиномиальной памятью. До сих пор неизвестно, совпадают ли какие-нибудь из перечисленных классов, однако, общепринятым является предположение о том, что все эти классы различны. Мы также будем придерживаться этого предположения.
С практической точки зрения особый интерес представляют задачи, содержащиеся в классе Р, поскольку для них существует полиномиальный решающий алгоритм, и они могут быть решены эффективно. Такие задачи мы будем называть полиполшалъиъши, а все остальные
Введение
— трудпорешаемыми. С теоретической точки зрения интерес представляют задачи, полные в том или ином классе, поскольку их сложность тем самым характеризуется наиболее точно.
Задача CSP является NP-полной [184], следовательно, в предположении P^NP, универсального полиномиального алгоритма для нее не существует. Однако многие подзадачи задачи CSP могут быть решены за полиномиальное время. Таким образом, второе направление состоит в выделении подзадач задачи CSP, для которых существует полиномиальный решающий алгоритм. Заметный вклад в разработку этой тематики внесли Й.Банг-Йенсен, М.Варди, Г.Готтлоб, М.Гроэ, М.Дайер, В.Далмау, Р.Дехтер, П.Джевонс, Ж.Диас, П.Йонссон, Ф.Колаитис, Д.Коэн, Н.Кренью, А.Крохин, М.Купер, Я.Нешетрил, М.Судан, М.Херрманн, Т.Федер, Е.Фройдер, С.Ханна, П.Хелл, Х.Чен и другие авторы.
Полученные здесь результаты имеют большое прикладное значение, так как многие практические задачи без ущерба могут быть ограничены таким образом, что они моделируются в терминах одной из таких полиномиальных подзадач (см., например, [145]) и потому могут быть решены за полиномиальное время. Кроме того, запас полиномиальных подзадач позволяет разрабатывать эвристики для универсальных сверхполиномиальных алгоритмов.
При изучении ограниченных подзадач задачи CSP применялся широкий спектр способов ограничения- условия на гиперграфы, соответствующие диофантовым формулам [39, 65, 100, 109, ПО, 111, 112, 114, 121, 146, 147], определимость в логиках различного типа [12, 54, 92, 117, 118, 152, 153, 155, 219], разнообразные комбинаторные условия [25, 35, 37, 38, 43, 68, 69, 98, 99, 138, 139, 140, 141, 144, 151, 164, 216], а также алгебраические свойства предикатов, вовлеченных в задачу [50, 137, 142, 144]. На сегодняшний день имеется более 300 работ, так или иначе связанных с этой областью.
Теоретическое значение исследований в третьем из перечисленных направлений состоит в том, что, записывая комбинаторную задачу в CSP-форме, мы можем получить ее полиномиальные подзадачи как "прообразы" полиномиальных подзадач CSP. Такой подход позволяет уточнить границу между полиномиальными и труднорешаемыми комбинаторными задачами. Большая работа была проделана в этом направлении в теории графов — в задачах, связанных с гомоморфизмами графов и разбиениями графов, см. монографию [126], обзор [125], а также статьи [87, 91]. Имеется тесная связь с некоторыми вопросами статистической физики (29, 30, 31, 32, 82, 94, 116, 169, 172, 173], а также дескриптивной теорией сложности [51, 54, 92].
Краткий обзор результатов, полученных до написания настоящей диссертации во всех трех направлениях, дан в следующем разделе.
В.2 Обзор предшествующих исследований
Цель данного обзора — охарактеризовать основные области исследований, связанных с задачей CSP, очертить круг возможных приложений, с тем чтобы затем показать место исследований, выполненных в диссертации, в общей картине.
/
Введение
В.2.1 Универсальные алгоритмы для задачи CSP
Впервые формализм задачи CSP был введен Монтанари в 1974 г. [184] для распознавания формы многогранников в проблеме машинного зрения. В этой работе он, в частности, ввел понятие сети ограничений как тройки, состоящей из множества переменных, множества возможных значений переменных и множества ограничений, накладываемых на допустичые комбинации значений переменных (ниже мы продемонстрируем, что сеть ограничений — лишь иное определение задачи CSP).
В последующие годы данный формализм был широко использован для моделирования самых разнообразных прикладных задач. В качестве примеров, составляющих лишь малую долю всего объема выполненных работ, назовем работы Аллена [5] по распознаванию естественных языков, Наделя и других [185, 18б[, использовавших CSP для технического проектирования и изучения семантики языков программирования, работы, исследующие задачи, связанные с пространственными и временными логиками, включая распознавание трехмерных сцен, см., например, [205].
На следующей фазе прикладных работ, связанных с задачей CSP, этот формализм был использован не только для единообразного моделирования других задач, но также и для разработки единых алгоритмов для их решения. Свое наивысшее развитие эта линия исследований нашла в создании специализированных декларативных языков программирования, таких, как ECLiPSe, Oz, 2LP, CHIP и Newton, а также библиотек и расширений универсальных языков программирования: ILOG (для C++), Prolog III и др., в которых для решения задачи достаточно записать ее в виде задачи CSP. Ясно, что основной проблемой в разработке таких языков являются универсальные алгоритмы для решения задач CSP.
Под эвристическими алгоритмами обычно понимаются алгоритмы, которые в основе своей используют метод "грубой силы", но используют различные ухищрения для сокращения пространства перебора. На сегодняшний день существует два подхода к созданию таких алгоритмов.
Первый подход заключается в усовершенствовании очевидного переборного алгоритма: переменным в некотором порядке присваиваются значения таким образом, чтобы уже присвоенные значения не нарушали ни одного из ограничений; если очередной переменной никакое значение присвоено быть не может, то алгоритм пытается изменить значение предыдущей переменной, и т. д. Этот алгоритм часто называют бжтрж-алгоритмолі. Было предложено множество разнообразных ухищрений, призванных ускорить работу бэктрэк-алгоритма, включая ограничения множества возможных значений для каждой переменной [24, 59, 67, 175], попытки угадать наиболее удачный порядок переменных при присваивании [14, 13, 132], а также оценить "удачность" значений для переменных [157, 124], использование различных методик машинного обучения [57, 101] и многие другие. Достаточно полный обзор результатов, достигнутых в этом направлении, можно найти в книгах [212] и [60]. Следует также отметить деятельность группы APES (Algorithms, Problems, and Empirical Studies) объединяющей более двух десятков исследователей из 6 стран, ведущей интенсивную работу по экспериментальной оценке различных усовершенствований бэктрэк-алгоритма.
Второй подход заключается в перекодировании произвольной задачи CSP к задаче CSP на двухэлементном множестве (существует несколько простых способов перекодировки), т.е. к задаче Выполнимость. Прогресс, достигнутый в решении задач Выполнимость за послед-
Введение
шіе два десятилетия, огромен (см., например, [79, 95, 178, 226, 227]), современные решатели для задачи Выполнимость способны решить, выполнима ли КЫФ, содержащая сотни тысяч переменных и миллионы элементарных дизъюнкции.
В [183] Митчелл показал, что практически все разновидности бэктрэк-алгоритма могут быть имитированы, если использовать хорошо известные техники решения задачи Выполнимость с минимальной (константной) потерей эффективности. Более того, он построил серию примеров задач CSP, решение которых с помощью соответствующих задач Выполнимость экспоненциально более эффективно, чем с помощью бэктрэк-алгоритма. Таким образом, единственный существующий на сегодняшний день разумный универсальный метод решения задач CSP — сведение их к задаче Выполнимость. Отметим также, что почти все коммерческие решатели CSP используют именно этот метод.
Сказанное выше относится, однако, лишь к универсальным переборным алгоритмам. Алгоритмы, решающие задачи CSP, полученные из конкретных прикладных задач и использующие особенности этих задач, как правило, значительно более эффективны, чем универсальные методы. Другие подходы к построению универсальных алгоритмов для CSP предусматривают интенсивное использование структуры задач CSP.
В.2.2 Подзадачи, решаемые за полиномиальное время
Исследование ограниченных задач CSP преследует две цели. Первая из них практическая — многие прикладные задачи выразимы в терминах ограниченных задач CSP и зачастую для них существуют алгоритмы, намного более эффективные, чем любой из универсальных алгоритмов. Вторая цель теоретическая — изучение сложности ограниченных задач CSP позволяет прояснить границу между полиномиальными и труднорешаемыми комбинаторными задачами. В этом разделе мы представим основные идеи и проблемы, имеющиеся в данной области; результаты, более тесно связанные с данной диссертацией, будут изложены в последующих разделах.
Существуют два основных пути задания ограничений на задачу CSP. Нам будет удобно использовать теоретико-модельное определение CSP как вопроса о существовании гомоморфизма из заданной конечной модели Q в заданную конечную модель И.. Для класса Г конечных моделей мы обозначаем через CSP(*,r) множество всех частных задач CSP, в которых модель It принадлежит Г, а через СЭР(Г, *) — множество частных задач CSP, в которых Q принадлежит Г. Если Г одноэлементен, скажем, Г = {7}, мы используем обозначение CSP(*,7) и CSP(7, *), соответственно. Возможны, разумеется, и комбинированные ограничения; соответствующие классы CSP будут обозначаться через С8Р(Гі,Г2).
Исторически первыми изучались ограничения вида CSP(r, *). Было показано, что если все структуры из Г удовлетворяют некоторым условиям, то задача CSP(r, *) может быть решена за полиномиальное время. Каждой модели может быть сопоставлен гиперграф, множеством вершин которого служит основное множество модели, а гиперребрами — элементы (кортежи) отношений модели; граф Гаифлшна модели получается из указанного гиперграфа, если соединить ребром каждую пару вершин, содержащихся в одном гнперребре. Среди рассмотренных условий были: ограниченная древесная ширина графа Гаифмана [3, 54, 152, 155, 153, 219] (мы вернемся к условиям этого типа в следующем разделе), представимость его в виде дерева графов ограниченной структуры [65, 100, 182], представимость гиперграфа, соответствующе-
Введение
го модели, в виде гипердерева гиперграфов ограниченной структуры [39, 109, 111, 112, 114], ацикличность гиперграфа [21, 22, 83, 113, 121], а также ряд других [57, 140, 146, 147]. Была также проделана определенная работа по нахождению методов, определяющих удовлетворяет ли данная модель одному из перечисленных условий [7, 11, 22, 56, 64, 66, 97, 98, 99, 102, 136], и по анализу эффективности различных методов [62, ПО, 156].
Изучение ограниченных задач CSP вида СЭР(*,Г) началось с пионерской работы Шефера [203], в которой он показал, что существует 6 множеств 2-элементных моделей, для которых эта задача может быть решена за полиномиальное время; если же класс 2-элементных моделей не принадлежит ни одному из этих множеств, то задача NP-полна. Этот результат получил название теорема Шефера о дихотомии. Позднее были предприняты попытки обобщить результат Шефера на множества произвольных конечных моделей. В частности, в [69, 138, 216] была показана полиномиальная разрешимость нескольких типов задач, обобщающих 2-Выполнимость, в [251, 35, 140, 144, 151] изучались обобщения задачи ХОРНОВСКАЯ выполнимость, статья [25] содержит некоторые результаты о моделях, отношения в которых выразимы с помощью операций полуколец, в [252, 38, 37] изучались классы моделей, которые могут быть представлены в виде объединения меньших моделей.
Наряду с задачей распознавания CSP интенсивно изучалась также связанная с ней задача #CSP о нахождении числа решений CSP, которая формулируется следующим образом: для условия Q,1Z обычной задачи CSP найти число решений, т.е. число гомоморфизмов из Q в TZ [31, 47, 48, 72, 73, 74, 82, 81, 80, 116, 133, 148, 170, 171, 194, 213, 215, 214]. Аналогично задаче CSP, эта задача также может быть ограничена с помощью указания двух классов разрешенных моделей. Имеется результат аналогичный теореме Шефера о дихотомии и показывающий, что каждая задача вида #CSP(*,r) либо полиномиальна, либо #Р-полна3 [47].
Отметим еще, что большой массив аналогичных исследований был выполнен для случая бесконечных моделей, главным образом моделей, элементами которых являются интервалы на вещественной прямой и открытые области на плоскости и в трехмерном пространстве. Внимание именно к этим типам моделей обусловлено их применимостью для решения задач во временной и пространственной логике. Поскольку изучение бесконечных моделей выходит далеко за рамки данной диссертации, мы ограничимся (неполным) списком работ, относящихся к этой области, - [4, 15, 40, 63, 75, 76, 77, 78, 106, 149, 158, 159, 160, 162, 187, 191, 197, 198, 205, 206, 217, 221, 222].
К настоящему времени сложились три основных подхода к изучению ограниченных задач CSP — логический, дискретно-математический и алгебраический. Мы обсудим эти подходы в пунктах В.2.3-В.2.5.
В.2.3 Логический подход
Первой точкой пересечения логики и задачи CSP является задача Выполнимость и ее обобщение задача Обобщенная выполнимость, в которой вместо элементарных дизъюнкций допускаются произвольные булевы предикаты. Обобщенная выполнимость может быть также определена как CSP(*, Г), где Г — класс всех двухэлементных моделей.
Важной вехой в исследовании логических аспектов задачи CSP явилась статья Федера и
Определение #Р-полноты приведено в разделе 1.3.
Введение
Варди [921. Мы рассмотрим ее более подробно, поскольку влияние этой статьи на последующие работы трудно переоценить: она содержит, иногда в зачаточном состоянии, большинство основных идей, развиваемых и поныне.
Прежде всего авторы, отталкиваясь от результата Шефера, показывают, что CSP образует максимальный синтаксически определимый подкласс NP, для которого возможна дихотомия. Любой больший класс задач эквивалентен всему классу NP в смысле полиномиальной сводимости, а значит, если P^NP, содержит задачи, не решаемые за полиномиальное время, но и не NP-полные [165]. Далее доказывается, что любая задача вида CSP(*,r) также полиномиально эквивалентна более узким классам задач: Н-Раскраска графа, Рбтракт графа и Ретракт
ЧАСТИЧНО УПОРЯДОЧЕННОГО МНОЖЕСТВА.
Следующей важной идеей, появившейся впервые в обсуждаемой работе Федера и Варди, является идея объяснения полиномиальной разрешимости задач вида CSP(*,r) с помощью некоторых логических формализмов. Говорят, что задача CSP(*,7c), где 7с — конечная модель, имеет ширину к, если класс моделей, не гомоморфных 7с, может быть определен с помощью программы на языке Даталог, каждое правило которой содержит не более к переменных Поскольку выразимость в Даталоге влечет также выразимость на языке первого порядка с оператором неподвижной точки, каждая такая задача CSP может быть решена за полиномиальное время [3] Показано также, что проблема, имеет ли CSP(*,7c) ширину 1, алгоритмически разрешима. Наконец, авторы построили широкий класс задач CSP, не имеющих конечноіі ширины. Все задачи из этого класса могут быть сведены к решению систем уравнений над конечной абелевой группой. Федер и Варди поставили задачу об описании конечных моделей 7с, для которых CSP(*,7c) имеет конечную ширину, и предположили, что конечную ширину не имеют в точности те задачи, с помощью которых могут быть смоделированы системы уравнений над конечными абелевыми группами. В [55] Далмау охарактеризовал задачи вида CSP(*,7c), имеющие ширину 1.
Понятие задач ограниченной ширины естественно распространяется и на задачи вида CSP(7c, *). Был получен ряд условий, эквивалентных конечности ширины [54, 152, 153, 155, 219]:
класс CSP(*,7c) [соответственно CSP(7c, *)] имеет ширину к;
существует программа на Даталоге, распознающая, верно ли, что не существует гомоморфизма данной модели в 7с [гомоморфизма из 7с в данную модель), и имеющая не более к переменных в каждом правиле;
класс моделей, для которых существует гомоморфизм данной модели в 7с [гомоморфизм из 7с в данную модель], выразим с помощью бесконечной экзистенциальной позитивной формулы, содержащей не более к переменных;
для любой модели Q в игре на гомоморфизм с к фишками на паре Q, 7с [на паре 7с, О] (определение см. в разделе 1.4) существует выигрышная стратегия для дуплнкатора тогда и только тогда, когда существует гомоморфизм из Q в 7с [гомоморфизм из 7с в Q);
7с обладает свойством древесной дуальности [обратной древесной дуальности]: для любой модели Q гомоморфизм из Q в 7с существует тогда и только тогда, когда каждая модель древесной ширины не более к, гомоморфная Q, гомоморфна также и 7с [гомоморфизм из 7с в Q существует тогда и только тогда, когда каждая модель древесной ширины не более к, гомоморфная 7с, гомоморфна также и Q].
Введение
Наивысшим достижением, полученным в рамках логического подхода, является характе-> ризация полиномиальных задач вида СЭР(Г, *). В [117, 118] Гроэ и другие показали, что при некоторых допущениях из теории параметризованной сложности задача СБР(Г, *) решаема за полиномиальное время тогда и только тогда, когда для некоторого к граф Гаифмана каждой модели из Г имеет древесную ширину, не превышающую к. В [117] Гроэ построил рекурсивный класс Г конечных моделей такой, что задача СЗР(Г,*) не является NP-полной и, если P^NP, не может быть решена за полиномиальное время. Для задач о подсчете числа решений Далмау показал [53], что #СБР(Г,*) может быть решена за полиномиальное время тогда и только тогда, когда древесная ширина графов Гаифмана моделей из Г ограничена.
Однако в изучении задач вида CSP(*, Г) этот подход оказался значительно менее эффективным. Кроме упомянутой серии эквивалентных условий, внимания заслуживает лишь один результат. Он касается выразимости класса конечных моделей, не гомоморфных некоторой фиксированной модели 'IZ, на языке первого порядка — отметим, что такая выразимость влечет полиномиальность задачи CSP(*,7?.). Атцерпас в [12] доказал, что указанный класс выразим на языке первого порядка тогда и только тогда, когда 7 обладает конечной дуальностью, т.е. существует конечное множество Д "запрещенных" конечных моделей такое, что модель Q не гомоморфна 72. тогда и только тогда, когда какая-нибудь модель из Д гомоморфна Q.
В.2.4 Дискретно-математический подход
Этот подход использует методы и результаты из различных областей дискретной математики, прежде всего теории графов Как уже отмечалось, большая часть комбинаторных задач может быть естественным образом сформулирована на языке CSP. Однако, исследования частных комбинаторных задач, как правило, слишком специфичны, не используют общих результатов о CSP. Одним из немногочисленных исключений явилась серия работ в теории графов [6, 10, 9, 8, 27, 26, 46, 45, 44, 73, 93, 115, 166, 168, 179, 199, 204, 223, 224, 225], в которой доказывалось, что большинство комбинаторных задач из теории графов решается за полиномиальное время для графов ограниченной древесной ширины. Многие из этих результатов могут быть выведены из того факта, что задача СБР(Г, *) решаема за полиномиальное время, если древесная ширина графов Гаифмана моделей из Г ограничена некоторым к [152]. С другой стороны, как мы увидим ниже, зачастую изучение частных комбинаторных задач служит источником идей для исследований по задаче CSP, а в некоторых случаях результаты, полученные для частных задач, имеют следствия, справедливые для общей задачи CSP. Мы остановимся лишь на тех комбинаторных задачах, взаимодействие которых с общей теорией CSP является особенно тесным.
Наиболее важной из таких задач является, безусловно, Я-РАСКРАСКА графа. Многие постановки в этой области близки к проблемам, возникающим при изучении общей задачи CSP. Классификация сложности этой задачи для ориентированных графов повлекла бы за собой классификацию сложности задач CSP(*,7) для произвольных конечных моделей, как показывает упомянутый результат Федера и Варди [92]. Хелл и Нешетрил в [127] доказали, что для неориентированного графа Я задача Я-Раскраска графа (т.е. CSP(*,iJ)) может быть решена за полиномиальное время тогда и только тогда, когда Я — двудольный граф, и NP-полна в противном случае. В случае ориентированных графов имеются частичные продвижения. В [120, 129] показано, что //-Раскраска графа решаема за полиномиальное время, если Я
Введение
— путь. Федер [85] показал, что дихотомия "Р - NP-полнота" справедлива в случае ориентированных циклов, однако, он не предложил критерия, различающего полиномиальный и NP-полный случаи. Отметим, что уже в случае ориентированных деревьев неизвестно, справедлива ли указанная дихотомия [128]. Банг-Йенсен, Хелл и МакДжилливрэй [19] показали, что если II содержит турнир в качестве подграфа, то Я"-Раскраска графа решаема за полиномиальное время тогда и только тогда, когда Я содержит не более одного ориентированного цикла. В [18] была сформулирована гипотеза о том, что это свойство является необходимым и достаточным для полиномиальное обсуждаемой задачи в случае, когда Я не содержит источников и стоков. Гипотеза была подтверждена в ряде частных случаев [18, 19, 20, 180, 181]. Любопытно, что во всех полиномиально разрешимых случаях полиномиальность может быть объяснена древесной дуальностью графа Я [128, 188).
Интенсивно изучались также некоторые варианты задачи Я-Packpacka графа, включая задачу Консервативная Я-PACKPACKA ГРАФА (в которой требуется определить, существует ли гомоморфизм из данного графа в Я такоіі, что каждая вершина о-юбражается в одну из вершин из заданного списка), а также соответствующие им задачи о подсчете числа решений (гомоморфизмов) #Я-Раскраска графа и Консервативная #Я-раскраска графа. В случае неориентированных графов имеется полная классификация для задачи Консервативная Я-раскраска графа [28, 86, 89, 90]; для задач #Я-Раскраска графа и Консервативная #Я-РАСКРАСКА графа такие классификации получены в [82] и [71, 73, 72], в обоих случаях критерий одинаков: задача может быть решена за полиномиальное время тогда и только тогда, когда каждая компонента связности Я — полный двудольный граф или полный граф со всеми петлями. Все упомянутые проблемы изучались также и в случае, когда в качестве исходных рассматриваются лишь графы из определенных классов, например, планарные графы или графы с ограниченными степенями вершин [70, 71, 73, 80, 82, 86, 103, 123, 181, 189].
Для некоторых задач из теории графов дихотомия "P - NP-полнота", по всей видимости, не имеет места. Так, в [91] было предложено записывать многие задачи из теории графов на языке так называемых консервативных разбиений. Этот формализм выразим в терминах задачи CSP, хотя и не в виде CSP(*,r). Однако соответствующая задача во многих случаях может быть сведена к достаточно длинной (псевдополиномиальной) серии задач CSP и — в случае, когда полученные задачи решаемы за полиномиальное время, — может быть решена за субэкспоненциальное время. Этот результат дает достаточно эффективные алгоритмы для многих задач из теории графов, о которых неизвестно, что они NP-полны, но неизвестен также и полиномиальный алгоритм. Далее, в [87] получена полная классификация задач о консервативных разбиениях, решаемых за псевдополипомиальное время. Наконец, в [88] эти результаты были обощены на случай общей задачи CSP.
Несмотря на достигнутые продвижения, основной трудностью, с которой сталкивается дискретно-математический подход, является недостаточность языка теории графов для описания свойств графов, определяющих сложность соответствующих задач. Так, результаты работ [28, 86, 89, 90] используют довольно громоздкие и не всегда прозрачные конструкции, а результаты из [87, 88] используют язык полиморфизмов, описанный в следующем разделе, их представление в теоретико-графовых терминах неизвестно.
Введение
В.2.5 Алгебраический подход
Этот подход к изучению задач вида СБР(*,Г) был предложен Джевонсом и его соавторами в [137, 142]. Он основан на использовании алгебраических свойств моделей из Г. Операция (возможно, многоместная) на основном множестве модели 72 называется полиморфизмом 72., если она сохраняет все отношения этой модели. Джевонс доказал, что для любых конечных моделей 72-1 и 7 если каждый полиморфизм 72-і является также полиморфизмом 7^, то CSP(72-o) сводится за полиномиальное время к CSP(7-i)4. Таким образом, сложность ограниченных задач CSP зависит исключительно от множества полиморфизмов соответствующих моделей.
Используя полиморфизмы, Джевонсу и другим удалось объяснить разрешимость за полиномиальное время многих известных классов CSP, а также значительно обобщить предшествующие результаты в этой области. Кратко охарактеризуем полученные результаты. Показано, что задача CSP(*,72.) может быть решена за полиномиальное время, если одна из следующих операций является полиморфизмом 72.: константная, полурешеточная, функция почти единогласия, аффинная операция х — у + z конечной абелевой группы. Результат о константных операциях расширяет класс непозитивных и ненегативных конъюнктивных нормальных форм из теоремы Шефера; задачи CSP, соответствующие моделям с полурешеточным полиморфизмом, включают в себя задачи с хорновскимп и анти-хорновскими КНФ, арифметическими ограничениями [218] и ограничениями, замкнутыми относительно взятия максимума [144]; задачи, соответствующие моделям, полиморфизмом которых является функция почти единогласия, обобщают задачу 2-Выполнимость, задачу CSP с импликационными ограничениями, а также класс CSP, названный O/1/All [140, 151]; наконец, задачи, соответствующие моделям с аффинным полиморфизмом позволяют решать системы линейных уравнений [140]. Позже Далмау [50] показал, что присутствие операций парапримальной алгебры в качестве полиморфизмов также влечет полиномиальную разрешимость соответствующей задачи CSP.
С другой стороны, NP-полные задачи CSP также получили объяснение на языке полиморфизмов: если модель 72. имеет лишь неконстантные унарные полиморфизмы, то задача CSP(*,72.) NP-полна. Это имеет место, например, в случае полных графов и, следовательно, применительно к задаче fc-PACKPACKA графа.
В случае задач о подсчете числа решений полиморфизмы также играют заметную роль. В частности, можно проверить, что теорема о дихотомии из [47] может быть сформулирована следующим образом. В случае, когда 72. — двухэлементная модель с основным множеством, например, {0,1}, задача #CSP(*,72.) может быть решена за полиномиальное время тогда и только тогда, когда операция х — у -|- z (mod 2) является полиморфизмом 72.; в противном случае эта задача #Р-полна.
Полиморфизмы были использованы в [51] при попытке охарактеризовать задачи CSP, решаемые с недетерминированной логарифмической памятью. В [139] показано, что если модель 72. имеет fc-местную функцию единогласия, то CSP(*,72.) имеет ширину к— 1. Наконец, в [36, 55] были введены понятия более общие, чем полиморфизмы. В первой из этих статей с помощью полиморфизмов удалось охарактеризовать задачи CSP ширины 1, а во второй — задачи CSP, решаемые с помощью некоторого специального алгоритма.
4Применением недавнего результата Рейнгольда [196] о том, что задача Достижимость в неориентированном ГРАФЕ может быть решена с логарифмической памятью, сводимость в этой теореме может быть ослаблена до сводимости с логарифмической памятью.
Введение
8.3 Цели работы
При внимательном рассмотрении логического и дискретно-математического подходов к изучению ограниченных задач CSP становится ясно, что при их использовании возникают значительные трудности, связанные с недостаточной выразимостью соответствующих языков. Это позволяет заключить, что, по-видимому, ресурс этих подходов к настоящему времени в известной мере исчерпан. Что касается алгебраического подхода, то его выразительные возможности выглядят более адекватными поставленным задачам. Трудности применения этого подхода связаны с огромным разнообразием возможных полиморфизмов. Однако до последнего времени не были использованы мощные методы изучения алгебраических операций, разработанные в современной универсальной алгебре. Поэтому представляется особенно актуальным привлечение для изучения задачи CSP методов и результатов универсальной алгебры.
Основная цель диссертации состоит в систематическом развитии алгебраического подхода к исследованию задачи CSP, а также применении разработанных методов к изучению сложности ограниченных задач CSP и задач, с ними связанных. Мы выделим несколько более конкретных целей.
A. Развитие разделов универсальной алгебры, изучающих строение алгебр с точностью до
термальноіі эквивалентности. Как станет ясно, особую роль здесь играет изучение ло
кальной структуры идемпотентных алгебр, а также свойств идемпотентных алгебр, ко
торые могут быть выведены из особенностей их локального строения.
Б. Использование алгебраического подхода для систематического изучения сложности ограниченных задач CSP, вплоть до исчерпывающего описания задач, решаемых за полиномиальное время.
B. Использование алгебраического подхода для систематического изучения сложности огра
ниченных задач о подсчете числа решений, вплоть до исчерпывающего описания задач,
решаемых за полиномиальное время.
Г. Применение разработанных методов и полученных результатов для исследования проблем дискретной математики и теоретической информатики, связанных с различными типами задач CSP.
8.4 Основные проблемы
В этом разделе мы сформулируем основные проблемы, рассматриваемые в диссертации.
В 1978 году Шефер [203] охарактеризовал все полиномиальные подзадачи Булева выполнимость, т.е. все классы Г двухэлементных моделей такие, что задача CSP(*,r) полиномиальна. В той же работе им была поставлена аналогичная проблема для классов произвольных конечных моделей.
Проблема 1С (Проблема классификации). Охарактеризовать классы Г конечных моделей такие, что задача СЗР(*,Г) полиномиальна [NP-полна].
Из результата Шефера следует также, что для каждого класса двухэлементных моделей соответствующая задача либо полиномиальна, либо NP-полна. Этот факт априори далеко не
Введение
очевиден, поскольку между классами Р и NP существует бесконечно много различных классов сложности. Как упоминалось выше, Федер и Варди в [92] поставили проблему, верна ли такая дихотомия для произвольных конечных моделей.
Проблема ID (Проблема дихотомии). Выяснить, верно ли, что для любого класса Г конечных моделей задача CSP(*, Г) либо полиномиальна, либо NP-полна.
Для приложений важно иметь метод, позволяющий распознавать, когда задача CSP(*,r) полиномиальна. Так как решение проблемы классификации само по себе может не обеспечить такой метод, актуальной является следующая
Проблема 1М (Проблема распознавания). Найти эффективный алгоритм, определяющий по данному классу Г конечных моделей, является ли задача CSP(*,r) полиномиальной.
Вероятнее всего, решение проблемы классификации обеспечит также и алгоритмы, решающие задачи CSP(*,r) тогда, когда они полиномиальны. Однако даже в этом случае найденные алгоритмы могут не быть максимально эффективными, например, в силу своей общности. Поэтому разработка алгоритмов, решающих полиномиальные задачи CSP(*, Г), является проблемой, заслуживающей особого внимания.
Проблема 1А (Проблема разработки алгоритмов). Разработать эффективные алгоритмы, решающие задачи вида CSP(*,T) в тех случаях, когда они полиномиальны.
Отметим, что для случая, когда Г — множество 2-элементных моделей, результаты работы [203] полностью решают проблемы 1С,ID. Все алгоритмы, необходимые для решения проблемы 1А в этом случае, были известны ранее (см. [104]). Наконец, проблема ЇМ в этом случае полностью решена в [154].
В статье [92] Федер и Варди отметили, что почти во всех известных случаях ограниченная задача CSP может быть решена с помощью "локальных" методов (в самой статье в качестве такого метода использовались программы на Даталоге). Известны также примеры задач, которые могут быть решены за полиномиальное время, но не могут быть решены локальными методами. Поскольку локальные методы являются наиболее широко распространенными при практическом решении задач CSP, следующая проблема представляет значительный интерес.
Проблема L (Проблема локальных методов). Охарактеризовать классы Г конечных моделей такие, что задача CSP(*, Г) может быть решена с помощью локальных методов.
В [47] (см. также [48]) Кренью и Херрман выполнили работу, аналогичную работе Шефера [203) для задач о подсчете числа решений. Это подсказывает, что для задач о подсчете числа решений могут быть сформулированы проблемы, аналогичные проблемам 1С, ID, ЇМ, 1А.
Проблема 2С (Проблема классификации). Охарактеризовать классы Г конечных моделей такие, что задача #CSP(*, Г) решаема за полиномиальное время [#Р-полна\.
Проблема 2D (Проблема дихотомии). Выяснить, верно ли, что для любого класса Г конечных моделей задача #CSP(*,F) либо полиномиальна, либо #Р-полна.
Проблема 2М (Проблема распознавания). Найти эффективный алгоритм, определяющий по данному классу Г конечных моделей, решаема ли задача #CSP(*, Г) за полиномиальное время.
Введение
Проблема 2А (Проблема разработки алгоритмов). Разработать эффективные алгоритмы, решающие задачи вида #CSP(*,r) в тех случаях, когда могут быть решены за полиномиальное время.
Третий блок проблем, рассматриваемых в диссертации, относится к методам изучения задач CSP. Как было упомянуто выше, мы концентрируем внимание на использовании методов универсальной алгебры для изучения задач CSP. Однако наиболее мощные из этих методов, такие, как теория ручных конгруэнции [131] и теория коммутаторов [96], имеют дело со структурой алгебр с точностью до полиномиальной эквивалентности, в то время как проблемы, сформулированные выше, требуют использования лишь термальных операций универсальных алгебр. Поэтому насущной представляется
Проблема Т. Развить методы исследования универсальных алгебр с точностью до термальной эквивалентности.
Проблема Т сформулирована весьма широко, однако позже мы уточним, какие аспекты этой проблемы наиболее важны для изучения задач CSP.
Оказалось, что для изучения задач о подсчете решений необходимо глубокое понимание структуры конечных мальцевских алгебр. Мальцевские алгебры были предметом интенсивных исследований на протяжении многих лет, см., например, [16, 34, 49, 119, 200, 202], а также монографию [207). Однако в нашем случае необходим ряд свойств подалгеб прямых степеней мальцевских алгебр с точки зрения их локальной структуры.
Проблема S. Изучить локальную структуру подпрямых произведений мальцевских алгебр.
В.5 Основные результаты
В диссертации решены проблемы 2С, 2D, 2А в полном объеме; проблемы 1С, ID, ЇМ, 1А, L решены в обширных частных случаях (для 3-элементных моделей, консервативных моделей и моделей, клон полиморфизмов которых минимален); проблема 1М решена в общем случае — при условии, что верна наша гипотеза, касающаяся проблемы 1С; получены существенные продвижения в решении проблем Т и S; проблема 2М осталась нерешенной. В таблице 1 для каждой из этих проблем указаны теоремы, которые дают ее решение (для проблем 1С, ID, ЇМ, 1А, L в указанных частных случаях) или продвижения. Частичное решение проблемы 1А дано
Таблица 1
алгоритмами, представленными в разделах 6.2, 8.2 и 9.6; решение проблемы 2А дано алгоритмом, представленным в разделе 15.4. Результаты, касающиеся изучения структуры конечных алгебр с точностью до термальных операций (проблема Т) содержатся в предложениях 10.1-10.6 и 11 1; результаты относительно структуры конечных мальцевских алгебр (проблема S) — в предложении 6.3 и леммах 6.3-6.7
Введение
Отметим, чго для обоих типов задач CSP (распознавания и о подсчете решений) решения проблем 1С и ID, а также проблем 2С и 2D даются одними и теми же теоремами. Ясно, что причина этого состоит в том, что для этих классов задач в изученных случаях справедлива дихотомия "Р - NP-полнота" [соответственно, "FP - #Р-полнота"). Однако, такого рода дихотомия и, следовательно, одновременное решение проблем 1С, ID [проблем 2С, 2D] имеет место далеко не всегда; например, в [117] получено описание всех полиномиально разрешимых задач вида CSP(r,*) и, вместе с тем, продемонстріфован класс Г, для которого CSP(r,*) не NP-полна, но и не может быть решена за полиномиальное время (если P^NP).
Как уже объявлено в разделе В.З, основополагающей идеей диссертации является использование универсальной алгебры для изучения задачи CSP. Прежде всего, мы показываем, что методы универсальной алгебры являются, по-видимому, наиболее адекватными для этой цели. Имевшиеся алгебраические результаты были недостаточными для изучения задачи CSP. В частности, как отмечено в предыдущем разделе, соответствующие алгоритмы требуют знания структуры конечных алгебр с точностью до термальной эквивалентности. Пополняя запас необходимых инструментов, мы показываем, что для каждой конечной алгебры такой, что многообразие, ею порожденное, избегает тип 1 в смысле теории ручных конгруэнции5, существует ее редукт, подалгебры которого образуют связный гиперграф, и многообразие, порожденное редуктом, имеет то же множество типов, в частности, избегает тип 1. Более того, даже если ограничиться подалгебрами очень простого вида — двухэлементными и изоморфными аффинной алгебре по модулю некоторой конгруэнции, — мы получим связный гиперграф. Далее, мы показываем, что операции указанных подалгебр могут быть продолжены до термальных операций исходной алгебры весьма регулярным образом. Набор возможных видов подалгебр отражает локальное строение алгебры, а получившийся гиперграф — ее глобальное строение. Найденные CSP-алгоритмы используют простые алгоритмы, работающие для подалгебр вышеуказанного ограниченного типа, и гиперграф алгебры —для того чтобы решить задачу CSP на всей алгебре.
Как станет ясно, для решения задач о подсчете решений необходима более детальная информация о строении мальцевских алгебр. Полученные в диссертации результаты показывают, что подпрямые произведения мальцевских алгебр обладают свойствами, сходными со свойством прямоугольности, более или менее сильными в зависимости от того, избегает ли алгебра тип 2. В критерии полиномиальности для задач о подсчете решений, теореме 15.1, мы используем новое условие на конгруэнции конечных алгебр в многообразии — конгруэнц-сингулярность. Это условие близко к условию регулярности конгруэнции, изучавшемуся ранее [96]. Конгруэнц-сингулярные многообразия уже встретили заинтересованное внимание специалистов по универсальной алгебре.
''Определения типов, фигурирующих в этой теории, приведены в разделе 2.3.
Введение
8.6 Основные методы
В доказательствах полученных в диссертации результатов используется широкий спектр методов. В соответствии с тем, что все результаты можно условно разделить на три большие группы — результаты о строении универсальных алгебр, доказательства трудности комбинаторных задач и построение полиномиальных алгоритмов, — в используемых методах можно выделить три типа.
Собственно универсально-алгебраические методы, включающие методы теории решеток, теории коммутаторов и теории ручных конгруэнции.
Методы теории сложности, т.е. сводимости различных видов, таких, как полиномиальная сводимость по Карпу, сводимость по Тьюрингу, сводимость с логарифмической памятью. Иногда нам приходится пользоваться некоторыми приемами полиномиальной арифметики и комплексного анализа. Отметим также, что часть сводимостей получена с использованием универсально-алгебраических результатов см., например, теорему 13.6.
Использование алгебраических понятий и фактов для построения комбинаторных алгоритмов. Типичным примером является использование условий из теории коммутаторов и теории ручных конгруэнции для построения алгоритмов для решения задач CSP распознавания над мальцевскими алгебрами и алгоритма для решения задач о подсчете решений.
8.7 Структура диссертации
Диссертация, кроме введения, имеет три главы (имеющие номера с 0 по 2), а также список литературы. Главы делятся на параграфы, имеющие сквозную нумерацию. Почти все параграфы делятся на пункты, нумеруемые двумя индексами, первый из которых означает номер параграфа. В некоторых случаях используется деление на подпункты, нумеруемые тремя индексами. В пунктах, на которые делится введение, роль первого индекса играет буква "В".
Охарактеризуем вкратце содержание каждой из глав. В главе 0 собрана вспомогательная информация, необходима для доказательства основных результатов диссертации. Глава 1 посвящена результатам о задачах распознавания CSP, а глава 2 задачам CSP о подсчете решений.
Результаты всех типов, также примеры и рисунки, имеют двухиндексную нумерацию, в которой первый индекс означает номер параграфа. Как и номерах пунктов, роль первого индекса во введении играет буква "В".
8.8 Апробация и публикации
Результаты диссертации были представлены на международных симпозиумах по автоматам, языкам и программированию (Женева, 2000; Турку, 2004), симпозиуме по теории вычислений (Херсонисос, 2001), международной летней школе по общей алгебре и упорядоченным множествам (Стржебске Плезо, 2001), международных конференциях по основам компьютерных наук (Ванкувер, 2002; Бостон, 2003), международной конференции по полугруппам, автоматам и языкам (Коимбра, 2002), международной конференции по универсальной алгебре и теории
Введение
решеток (Нэшвнлл, 2002), международной конференции по алгебре (Лиссабон, 2003), международной конференции по искусственному интеллекту (Акапулько, 2003), международных симпозиумах по логике в компьютерных науках (Оттава, 2003; Турку, 2004), международной конференции по теории и практике задач CSP (Кннсале, 2003), международной школе но раскраскам графов (Дагштуль, 2003), международных школах по задачам CSP (Монреаль, 2004; Оксфорд, 2006; Дагштуль, 2006; Нэшвилл, 2007), международной алгебраической конференции (Екатеринбург, 2005). Автор выступал с докладами о результатах диссертации на семинарах технического университета Дрездена (2001), университета Лондона (2001,2004), университета Монреаля (2002), университета Ливерпуля (2002), университета Эдинбурга (2003), университета Воррика (2004), университета Саймона Фрейзера (2004, 2005, 2006), на семинаре "Алгебра и логика" в Новосибирске (2005,2006), и на семинаре "Алгебраические системы" в Екатеринбурге (2000-2006).
По теме диссертации опубликовано 23 работы [228]-[250], из которых 13 работ [228, 229,
231, 233, 234, 236, 237, 241, 242, 243, 249, 250] являются совместными. В статьях [241, 230,
233], а также тезисах конференций [228, 233], автору принадлежит подавляющая часть доказательств. В работе [250] и соответствующих тезисах конференций [236] автору принадлежат доказательства всех результатов, исключая сведение к случаю идемпотентных алгебр. Статьи [234, 242] являются обзорами, в статье [229] автору принадлежит результат о полино-мнальностн алгебр с минимальным клоном термальных операций, порожденным операцией консервативного коммутативного группоида. Заметим, что результаты этой статьи были значительно обобщены в [239]. В статье [249] приводится упрощенная, хотя и менее мощная, версия алгоритма из [245]; эта статья написана в нераздельном соавторстве с В. Далмау. Работа тезисы на конференциях [237]) написана в нераздельном соавторстве с М. Гроэ.
Работы [251]—[256] содержат результаты, тесно связанные с темой диссертации, по не вошедшие в текст диссертации.
Автор считает приятным долгом выразить глубокую благодарность Льву Наумовичу Шев-рнну за постоянное стимулирующее внимание и всестороннюю поддержку. С благодарным чувством я вспоминаю своего первого учителя Евгения Витальевича Суханова, многолетнее сотрудничество с которым сыграло неоценимую роль в моем научном становлении. Я благодарен П. Джевонсу, который в свое время привлек мое внимание к задачам CSP, за продолжительное и плодотворное сотрудничество, а также М. В. Волкову, В. Б. Репнпцкому и другим участникам руководимого Л. II. Шеврпным семинара "Алгебраические системы" за многочисленные полезные обсуждения, в немалой степени способствовавшие исследованиям, отраженным в диссертации.
Основные понятия теории сложности
Мы дадим лишь самые основные определения из теории сложности. Напомним, что комбинаторной задачей распознавания называется задача, сформулированная в виде вопроса, ответ на который — "да" или "нет". Поскольку условие любой задачи может быть закодировано в виде слова над некоторым конечным алфавитом, каждая задача распознавания может быть представлена в виде языка над конечным алфавитом, состоящего пз всех возможных условий задачи, ответом на которые является "да". Таким образом, задача распознавания — это всегда задача о том, принадлежит ли данное слово некоторому фиксированному языку. Размером задачи называется длина слова-условия. Через Р обозначается класс всех задач распознавания, которые могут быть решены детерминированной машиной Тьюринга за полиномиальное время. Задачи из Р мы будем называть полиномиальными. Класс NP содержит задачи распознавания, решаемые за полиномиальное время недетерминированной машиной Тьюринга. Нам потребуется также еще одно эквивалентное определение этого класса. Пусть — конечный алфавит, — множество всех слов над ; через \w\ мы обозначаем длину слова w Є . Бинарное отношение R на называется полиномиально сбалансированным, если существует полином р такой, что для любой пары (u,v) є R справедливо неравенство гі pd l); отношение ft называется полиномиально разрешимъш, если существует детерминированная машина Тьюринга, которая для любой пары (u,v) Є S X Е за полиномиальное время решает, принадлежит ли данная пара отношению R. Класс NP состоит из всех языков L над конечным алфавитом, для которых существует полиномиально сбалансированное и полиномиально разрешимое отношение R такое, что L = {и Зи(и,и) Є R}
Существуют два наиболее широко используемых типа сводимости между задачами распознавания. В обоих из них задача распознавания языка L над алфавитом X сводится к задаче распознавания некоторого языка М над конечным алфавитом G, если существует отображение /: — 0 такое, что и є L тогда и только тогда, когда f(u) Є М. Для сводилюсти за полиномиальное время необходимо, чтобы / было вычислимо за полиномиальное время; для сводимости с логарифмической памятью требуется, чтобы / было вычислимо машиной
Тьюринга с логарифмической памятью. Задача называется NP-трудной, если к ней сводится любая задача из NP. Если NP-трудная задача принадлежит NP, то она называется NP-полной. Ясно, что эш понятия зависят от используемого типа сводимости. Любая задача, NP-полная [NP-трудная] в смысле сводимости с логарифмической памятью, является также NP-полной [NP-трудной] в смысле сводимости за полиномиальное время. В большинстве случаев верно и обратное Мы будем стремиться использовать более слабую сводимость с логарифмической памятью. Отметим еще, что для сводимости с логарифмической памятью имеет смысл говорить о Р-полных задачах, определяемых аналогично NP-полным задачам. Стандартным примером Р-полной задачи является ХОРНОВСКЛЯ Выполнимость.
Каждой задаче распознавания L из класса NP можно поставить в соответствие задачу о подсчете числа решений следующим образом. Пусть R — полиномиально сбалансированное и полиномиально разрешимое отношение, соответствующее L. Тогда в задаче #L для данного v требуется найти число #и элементов в множестве {v \ (u,v) Є R}. Очевидно, #-L зависит также от выбора отношения R, однако во всех случаях, с которыми мы будем иметь дело, этот выбор является "наиболее естественным". Задачи вида #L для всевозможных L Є NP образуют класс #Р. Совокупность задач о подсчете числа решений, решаемых за полиномиальное время, образует подкласс класса FP задач о вычислении функций вида /: Е - N, решаемых за полиномиальное время.
Как и в случае задач распознавания, существуют два основных типа сводимости между задачами о подсчете числа решений. Скупой сводимостью задачи #L над алфавитом S к задаче #М над алфавитом в называется полиномиально вычислимая функция /: Е -» 0 такая, что #и = #/(гі) для всех и Є Е - Задача фЬ сводится к #М по Тьюрингу, если существует решающая #L машина Тьюринга, использующая #М в качестве оракула и работающая полиномиальное время (каждый вызов #М считается одним шагом). Однако ни один из указанных типов сводимости не может бьиь признан удовлетворительным. Скупая сводимость слишком слаба и не позволяет выяснить сложность многих задач, представляющих практический интерес. Сводимость по Тьюрингу слишком сильна и позволяет сводить к задачам из #Р задачи, там не содержащиеся [211]. Тем не менее, сводимость по Тьюрингу является наиболее используемым типом сводимости при изучении задач о подсчете числа решений. Мы также будем использовать этот тип сводимости. Задача называется #Р-трудной, если любая задача из Ц-Р сводится к ней по Тьюрингу. Отметим, что #Р-трудными могут быть и задачи о вычислении функций, не являющиеся задачами о подсчете числа решений. Задача называется #Р-полной, если она #Р-трудна и содержится в #Р. Ряд примеров #Р-полных задач мы приведем в разделе 1.3.
Пусть А — конечное множество. Под п-местнъш отношением на А, как обычно, понимается произвольное множество кортежей длины п элементов из А (п-кортежей); ША обозначает множество всех конечноместных отношений на А. Компоненты те-кортежа а будут обозначаться через а[1],... ,а[п]. Определение 1.1. Задача CSP — это задача распознавания, условием которой является тройка V — (V\A\C) где V — конечное множество переученных, А — множество возможных значений, С — множество ограничений, в котором каждое ограничение С Є С представляет собой пару {s,R}, где s — список переменных длины тс, называемый областью ограничения, a R — это тос-местное отношение на А, называемое отношением ограничения. В задаче CSP спрашивается, существует ли решение для V, т.е., отображение р: V — А такое, что для каждого ограничения из С образ области ограничения является кортежем, содержащимся в отношении ограничения. Размером частной задачи CSP мы считаем длину строки над подходящим алфавитом, содержащей список всех областей ограничения, а также список всех кортежей для каждого отношения ограничения.
Пример 1.1 (Выполнимость). Условием стандартной задачи Выполнимость из логики высказываний [104, 190] служит формула логики высказываний Ф = Х\ Л Л Хп в конъюнктивной нормальной форме; спрашивается, выполнима ли Ф. Как нетрудно видеть, эта задача эквивалентна задаче CSP с условием (V, {0,1},С), где V — это множество переменных, встречающихся в формуле Ф, и С = {(si,i?i),... ,(sn,i?n)}, каждая из областей ограничений s, представляет собой список переменных, участвующих в элементарной дизъюнкции Xi, a R\ состоит из всех булевых кортежей, удовлетворяющих элементарную дизъюнкцию Хг.
Пример 1.2 (К-РАСКРАСКА ГРАФА). Пусть Н — (ориентированный) граф. В задаче 7Ї-РАСКРАСКА ГРАФА спрашивается, существует ли гомоморфизм из данного графа Q в Ті.
Каждый (ориентированный) граф Н = (V(H),E(H)) соответствует бинарному отношению Rj{. (а, Ь) Є RH тогда и только тогда, когда (а, Ь) — дуга Н. Тогда каждый частный случай Q — (V(g); Е{9)) задачи Н-РАСКРАСКА ГРАФА соответствует задаче CSP с условием {V(Q);V(H); {((a,b),RH)\{a,b)&E(g)}). Если Н — полный граф с к вершинами, то, как легко видеть, задача Ті-РАСКРАСКА ГРАФА эквивалентна задаче /С-РАСКРАСКА ГРАФА В [92] Федер и Варди заметили, что задача CSP может быть сформулирована в виде проблемы о гомоморфизме конечных моделей. Напомним, что сигнатурой называется множество реляционных символов {Ri ] і Є /}, каждый из которых имеет фиксированную арность1. Моделью сигнатуры {Ri \ і Є 1} называется пара ТЇ = (Н; {й і Є /}), где Н — непустое множество (носитель TL), а каждое R является отношением на Н, имеющее ту же арность, что и символ Ri. Пусть Q,TL — модели одинаковой сигнатуры {Rl \ і Є /}. Гомоморфизмом из Q в Н называется отображение :(3- Я такое, что для каждого отношения RP модели Q и каждого кортежа (а[1],... ,а[т]) Є Rg выполняется условие ( (а[1]),... ,у(а[т])) Є RH.
Свойства мальцевских алгебр
В теории ручных конгруэнции каждой паре конгруэнции а - /? (т.е. такой, что (3 покрывает а) конечной алгебры А присваивается один из 5 типов. Пусть основное множество алгебры А обозначается через А. Множество U С А называется (а, (3)-минимальным множеством, если оно минимально относительно включения среди подмножеств из А, которые могут быть представлены в виде f(A), где / — унарный полином А такой, что /(/3) % а. Пусть, далее, Т = ВГ)11 для некоторого /3-класса В такого, что Т2 а- Тогда Т называется (а,(3)-следом, а алгебра Т = AL = (T;F), где F — {/L / — полином А, сохраняющий Г}, называется индуцированной алгеброй. Алгебра Т/а , полиномиально эквивалентна алгебре одного из следующих пяти типов, которые отражают особенности локального строения А: 1 конечное G-множество, т.е. множество с действующей на нем группой; 2 конечное векторное пространство; 3 двухэлементная булева алгебра; 4 двухэлементная решетка; 5 двухэлементная полурешетка. Тип индуцированной алгебры Т/ \ зависит только от конгруэнции а, (3 и не зависит от выбора следа. Таким образом, этот тип может быть присвоен паре (простому интервалу) (а,/?). Тип простого интервала обозначается через typ(a,/3). Далее, typ(A) = {typ(a,/?) а,(3 G Соп(А), a (3}\ и для класса конечных алгебр 21 положим typ(2l) = иА21 Р( )- Если для конечной алгебры А [класса конечных алгебр 21] имеет место і 0 typ(A) [і typ(2l)j, то мы говорим, что А [соответственно 21] избегает тип . Простые интервалы решетки конгруэнции мальцевской алгебры могут иметь лишь типы 2 и 3. Пусть А — мальцевская алгебра и а - j3 — ее конгруэнции. Класс конгруэнции а, содержащий элемент а, мы будем обозначать через аа. Операция алгебры А/а, соответствующая операции / алгебры А, будет обозначаться через /а. Пусть также (3/ обозначает конгруэнцию алгебры А/а, определенную следующим образом ([130, 96]): (аа,Ьа) Є (3/а тогда и только тогда, когда (а,Ь) є (3. Следующее предложение отчасти следует из результатов [130, 96] и теоремы 8.5 [131], а отчасти является фольклором. Предложение 2.7. Пусть А — мальцевская алгебра, d — ее мальцевский терм и а - (3 — ее конгруэнции. (1) Минимальные мнооюеетва малъцевких алгебр являются объединением следов. (2) typ(a,/3) = 2е том и только в том случав! когда для любого (3 /а-класса В алгебры А/а и любого а Є А/а алгебра (B;da(x,a,y),da(a,x,a),a) является абелеоой группой; в противном случае typ(a,/3) = 3.
Еще одно несложное утверждение содержит три простых свойства мальцевских алгебр, которые мы будем часто использовать. Пусть п — натуральное число, тогда п обозначает множество {1,... ,п}. Для кортежей а = (а[1],... ,а[га]) и b = (b[l],... ,b[m]), через (a,b) обозначается кортеж (а[1],... ,a[n],b[l],... ,b[m]), а через (а,Ь) — пара кортежей. Отметим еще, что подалгебры прямых степеней алгебры могут рассматриваться как отношения, инвариантные относительно основных операций алгебры. Поэтому мы будем использовать для таких подалгебр некоторые обозначения, введенные для отношений. Предложение 2.8. Пусть Е — подпрямое произведение мальцевских алгебр В і,... , В п и пусть I С п. 1. Ю прямоугольно, т.е. если a,b Є prjD,c,d Є prn_/D и (а,с), (a,d),(b,c) Є Ш , то (b,d)eP. 2 Отношение 9i = {(a,b) Є (рг/D)2: существует с Є prn_jlB такой, что (a, c),(b,c) Є D} является конгруэнцией алгебры prjH . 3. D является дизъюнктным объединением, множеств вида В X С, где В — это ві-класс и С — это вп 1-класс. Как обычно, наименьшая нетривиальная конгруэнция подпрямо неразложимой алгебры называется монолитом. Нам потребуется следующее свойство монолитов подпрямо неразложимых мальцевских алгебр. Предложение 2.9. Пусть А — подпрямо неразлооюимая мальцевская алгебра, р. — ее монолит и а ф Ь. Тогда для любых c,d Є А таких, что (с, d) Є Ц найдется термальная операция /(ж, г/!, ...,уп) и еь... ,еп Є А такие, что /(а,еі,... ,е„) = с, f{b,e\,... ,en) = d.
В то время как в общем случае строение простых конечных алгебр практически не исследовано, имеется некоторая информация о структуре конечных простых идемпотентных алгебр, а также исчерпывающее описание строго простых идемпотентных алгебр. Напомним, что алгебра называется сюръективной, если все ее термальные операции сюъ-ектнвны. полным, идемпотентнъш редуктом алгебры A = (A; F) называется алгебра ld(A) = (A; F ), где Fjd обозначает множество всех идемпотентных термальных операций А. Элемент а алгебры А называется поглощающим, если для любой (п+ 1)-местной термальной операции t(x,yi,... ,уп) алгебры А такой, что t зависит от ж, и любого набора значений (6і,...,6п) Є Ап имеем t(a, b\,... ,bn) = а. Конгруэнция в алгебры Afc называется косой, если она не является ядром гомоморфизма, переводящего каждый кортеж (0.1,...,) Є Ak в (a,,,...,ait), где {ч,... ,ig} С {I,... ,k} — некоторое фиксированное множество. Предложение 2.10 ([150]). Если А — конечная простая идемпотентная алгебра, то верно одно из следующих утверждений: (а) А термально эквивалентна модулю; (Ь) А имеет поглощающий элемент; (с) А не имеет косых конгруэнции для всех к. Конечная алгебра называется строго простой 2, если она проста и все ее собственные подалгебры одноэлементны. А. Сендреи в [210] получила исчерпывающее описание все конечных строго простых алгебр (не только идемпотентных). Чтобы сформулировать этот результат, нам потребуется несколько определений и обозначений. Пусть О — группа перестановок, действующая на множестве А. Через R(G) мы обозначаем множество операций на А, сохраняющее отношения вида {(a,g(a)) \ а Є А}, где д Є G, а через F(G) — множество идемпотентных операций из R(G). Напомним, что группа перестановок G, действующая на А называется регулярной, если для любых а,Ь Є А найдется д Є G такой, что д{а) = Ь, и любая нетождественная перестановка из G не имеет неподвижных точек. Группа G называется примитивной, если алгебра (A,G) проста. Пусть к А = (А;+, К) — конечномерное векторное пространство над конечным полем К, Т(А) — группа трансляций {х + а \ а Є. А} и End к А — кольцо эндоморфизмов провтранства к А. Тогда А может рассматриваться как модуль над End к А. Этот модуль обозначается через (End КА)Л Наконец, пусть F обозначает множество всех операций, сохраняющих отношение Х% {(а\,..., аі) Є А аг = 0 по крайней мере для одного индекса г, 1 і к}, где 0 — некоторый фиксированный элемент из А. Пусть также F = Пь 2 ; Предложение 2.11 ([210]). Пусть А — конечная строго простая сюръективная алгебра. Если А не имеет одноэлементных подалгебр, то А термально эквивалентна одной из следующих алгебр: (a) (A,R(G)), где G — регулярная группа перестановок, действующая ни А; (b) (Л, Termid(/End к д\А) UT(i)), где / А — (А;+,К) — конечномерное векторное про-странство над конечнъш полелі К; (с ) (A,G), где G — приліитивная группа перестановок, действующая на А. Если А имеет одноэлементные алгебры, то А идемпотентна и термально эквивалент на одной из следующих алгебр: (а) (A,F(G)), где G — группа перестановок, действующая на А и такая, что каждая нетооїсдественная перестановка из G имеет не более одной неподвижной точки; (b) (Л, Тегт1сі(/Епс1 дчУІ)), где кА — конечномерное векторное пространство над конечнъш полем К; (d) (A, F(G)nF) для некоторого к (2 к ш), некоторого элемента 0 Є А и некоторой группы перестановок G, действующей на А, таких, что 0 — единственная неподвимс-ная точка каждой нетождественной перестановки из G; (e) (A,F), где \А\ — 2 и F содержит полурешеточную операцию; (f) 2-элементная алгебра с пустым множеством основных операций.
В главе 0 было показано, как полиморфизмы отношений и конечных моделей помогают в исследовании сложности задач CSP. В этом параграфе мы разовьем данный подход, продемонстрировав в разделе 3.1, что сложность задач CSP тесно связана со свойствами конечных алгебр, а также многообразий, ими порожденных. В разделе 3.2 мы введем многосортную задачу CSP — обобщение и основной формализм, используемый в большинстве последующих доказательств. Там же будет показано, как алгебраический подход применяется в случае многосортных задач, а также приведено несколько результатов, связывающих обычные и многосортные задачи CSP. Наконец, в разделе 3.3 мы введем три уровня полнномиалыгости задач CSP, в зависимости от того, насколько широко определяются классы таких задач.
От клонов функций к алгебрам и далее к многообразиям алгебр
Установленная в разделе 2.2 связь между сложностью задач CSP и клонами функций, позволяет легко установить аналогичную связь между CSP и конечными алгебрами. В частности, мы можем распространить понятия полиномиальности и NP-полноты на конечные алгебры. Определение 3.1. Алгебра A = (A\F) называется полиномиальной [NP-полной], если множество InvF полиномиально [NP-полно]. Поскольку множество инвариатных отношений множества F и аналогичное множество для клона отношений, порожденного F, равны, термально эквивалентные алгебры полиномиальны [NP-полны] или не полиномиальны [не NP-полны] одновременно. Наша первая цель — выявить, какие свойства алгебр ответственны за их полиномиалыюсть [NP-иолноту]. Оказывается, полиномиалыюсть выдерживает действие стандартных алгебраических операторов. Теорема 3.1. Пусть А — конечная алгебра. (і) Если А полиномиальна, то любая подалгебра, любой гомоморфный образ и любая конечная прямая степень алгебры А также полиномиальны. (ii) Если у А есть NP-полная подалгебра или NP-полный гомоморфный образ или NP-полная конечная пряліая степень , то А также NP-полна. Доказательство. Рассмотрим сначала случай подалгебр. Пусть В = (B,F\B) подалгебра алгебры A = {A,F). Легко видеть, что lnv(Fs) Я Inv(F). Следовательно, CSP(lnv(Fjg)) сводима к CSP(lnv(F)) за константное время. Утверждения (і) и (іі) в случае подалгебр следуют из существования этой сводимости. Пусть В = (B,FB) — гомоморфный образ алгебры А = (A,FA) и ip — соответствующий гомоморфизм. Мы покажем, что для любого конечного Г С \nv(FB) задача СЭР(Г) сводима за линейное время к СЭР(Г ) для некоторого конечного Г С \nv(FA). Для отношения Д Є lnv(FB) положим у _1(Д) = {а ір(а) Є R}, где ip действует покомпонентно. Очевидно, tp l (R) — отношение той же арности, что и Л. Непосредственно проверяется, что -1(-Я) Є \nv(FA). Положим Г = { -1(Д) R Є Г}. Тогда Г — конечное подмножество из \nv(FA). Для частной задачи V = (V,B,C) из CSP(r) мы строим задачу V = (V,A,C) из CSP(r ), где С = {(s, p-l(R)) (s,R) Є С}.
Если отображение ф является решением V, то рф — решение V. Обратно, если — решение V, то любое отбражение ф : V — А такое, что рф(у) = (и) для всех v Є V, является решением Vі. Пусть теперь Ш = (B,FB) = Afc, где А = (A,FA). Каждый элемент а множества В может быть отождествлен с кортежем (11,...,) длины к элементов из А, каждый кортеж а = («і,..., «„) — с кортежем а = (an,..., a\k, 021,... , a„;c) длины пк, где aj = (a,i,..., atfc); наконец, n-местное отношение Д над В отождествляется с отношением Д = {а а Є Д} над А. Для частной задачи V = (V,B,C) из CSP(lnv(FB)) мы строим задачу V = (V ,A,C) из CSP(lnv(F4)), где V содержит к копий vy,... , каждой переменной v Є V, а С = {(s , R ) \ (.5, Д Є С}, где s = (иц,..., vik, voi,..., vnk) при s = (г і,..., и„). Нетрудно видеть, что если отображение ч/ является решением Р, то отображение ф : V — /1, для которого ф {уг) = а,, где (w) = (аь ;afc) является решением Vі. Обратно, если — решение Vі, то любое отбражение ф : I7 — J4 такое, что V (w) = ((ui) ()) для всех и Є V, является решением V. Следствие 3.1. Алгебра из псевдомногообралія, порожденного полиномиальной алгеброй, полиномиальна. Как хорошо известно, псевдомногообразие, порожденное конечной алгеброй, совпадает с классом конечных алгебр из многообразия, порожденного ею. Следствие 3.2. Конечная алгебра из многообразия, порожденного полиномиальной алгеброй, полиномиальна. Таким образом, полиномиальность — это свойство, определяемое тождествами! Более того, из доказательства теоремы 3.1 можно заключить, что NP-полнота также зависит только от тождеств, выполняющихся в алгебре. Следствие 3.3. Если многообразие, порожденное конечной алгеброй А, содержит конечную NP-полную алгебру, то А также NP-полна.
Как правило, алгебры, возникающие при изучении задач CSP, имеют мало общего с классическими алгебрами, такими, как группы, полугруппы, кольца. Поэтому не следует ожидать, что полиномиальность или NP-полнота определяются какими-либо хорошо известными типами тождеств. Некоторые предположения о виде тождеств, ответственных за сложность задач CSP, мы выдвинем в разделе 4.2.
Следующим шагом является ограничение класса алгебр, требующих изучения. Пусть А = (A; F) — конечная алгебра, е — унарный идемиотентиыи терм (т.е. удовлетворяющий равенству е(е(х)) = е(х)) и U = е(А). Тогда алгебра В = (U;Fe), где Fe = {/I / термальная операция А и f(U,. ., С/) С (/}, называется термально индуцированной для А. Предложение 3.1. Пусть А — конечная алгебра и В — алгебра, термально индуцированная для А. Тогда существует сведение за полиномиальное время задачи CSP(A) к CSP(B) и обратно. В частности, А полиномиальна [NP-полна] тогда и только тогда, когда Ш поли-номиальна [NP-полна]. Доказательство. Пусть U — подмножество А, равное е(А) для некоторой термальной унарной пдемпотентной операции є Є Term (А). Пусть также Г — конечное множество отношений из lnv(Term(Ay)). В первой части доказательства мы покажем, что задача CSP(F) сводится за линейное время к CSP(r ), где Г — некоторое конечное подмножество из Inv(F). Пусть V = (V, U,C) — частная задача из СЭР(Г). Для любого m-местного отношения і? є Г мы обозначаем через В! отношение на А, определенное следующим образом: R = { ?(ai,. . ,afc) I k 0, дЄ Term(A), ab...,afc Є R]. Чтобы показать, что R Inv(F), возьмем (тг-местную) операцию / Є F и набор кортежей b i,...,bn R . Каждый кортеж Ьг может быть представлен в виде Ьг = і(аг[1], )аЛ гг]) где 0, Є Term(A) и а,[1],... ,а,[/с,] Є R. Операция g = f{g\{xn,---,xikl),.,. ,gn{xni,... ,xnkn)) принадлежит Term(A), поэтому /(bb...,b„) = g(a.i[l],... ,аг[кі],... ,an[l],... , Хп[кп]) Є R . Обозначим Г = {R1 \ R є Г} п положим V = (V,A,C), где С = {{s,R ) ] (s,R) Є С}. Очевидно, что V — частная задача из CSP(r ) и, поскольку Г фиксировано н конечно, она может быть получена из V за линейное время. Так как Term(A) содержит все проекции, имеем R С R , а значит каждое решение задачи V является также решением задачи Vі. Пусть теперь ф является решением задачи Vі. Мы докажем, что е-ф является решением задачи V. Для этого достаточно проверить, что e(R ) С R. Пусть а R . Тогда е(а) = e ?(ai,..., а ;) для некоторой операции g Є Term (А) и некоторых кортежей ai,..., а . є R. Операция ед{х\,..., хк) сохраняет U и принадлежит Term(A); следовательно, ее ограничение на U принадлежит Term(A)[/ = Term(Ar/). Поскольку R є lnv(Term(A[/)), мы получаем е(а) Є R. Мы показали, что СБР(Г) сводима за линейное время к CSP(r ) и, следовательно, полиномпальность алгебры А влечет полиномпальность алгебры Ау, а NP-полнота Ау влечет NP-иолноту А.
Утверждается, что если задача V имеет решение ф, то она имеет решение ф, для которого ф[уа) = а для всех а Є А. Для доказательства этого заметим, что существует / Є G со свойством ф(уа) = /(а) для всех о Є А. Так как G является группой, она содержит обратную операцию /-1 є G, а значит ф = /_1г есть решение задачи V и / 1ф(уа) = а для всех а Є А.
Любое решение ф, обладающее этим свойством, удовлетворяет всем ограничениям в С, поэтому ограничение ф на V является решением Р. Обратно, если ф есть произвольное решение задачи V, то его расширение ф на V такое, что ф (уа) = а для всех а Є Л, является решением Vі. Таким образом, эта конструкция является полиномиальной сводимостью CSP(lnv(F) UC) к CSP(lnv(F)).
От множеств отношений к клонам отношений и далее к клонам функций
Как и прежде, основная идея состоит в том, чтобы сократить количество множеств отношений, требующих изучения, рассматривая лишь множества отношений, замкнутые относительно некоторых операций. В дальнейшем мы увидим, что такими замкнутыми множествами вновь являются клоны отношений, однако, это потребует значительно больших усилий, чем в случае задач распознавания. Отметим, что аналогичный подход для задач о подсчете числа решений был использован в [47, 48] для отношений над 2-элементным множеством. В этих работах использовалась конструкция, названная авторами достоверным представлением. В качестве первого шага в развитии алгебраического подхода к #CSP мы вводим следующее понятие, которое эквивалентно достоверному представлению при \А\ = 2 и тесно связано с представлением частных задач #CSP в логической форме.
Пусть Г — множество отношений над конечным множеством А. Отношение R, определяемое конъюнктивной формулой Ф(у\,... ,Vk) со свободными переменными VI,..., Vk, есть /г-местное отношение, состоящее из кортежей ( p{vi),..., (f{vk)) для каждого присваивания f переменных, для которого формула Ф истинна. Если Ф включает в себя только предикаты из Г, мы говорим, что Q определяемо конъюнктивной формулой над Г. Как обычно =д обозначает отношение равенства на множестве А.
Пусть теперь V является частной задачей задачи #СБР(Ги {=д}). Для того чтобы избавиться от отношений равенства =д мы используем процедуру из [137], удаляя каждое ограничение вида =А {u,v) из V и заменяя каждое вхождение переменной v на и.
Полученная задача V принадлежит #СБР(Г). Легко видеть, что эта процедура может быть выполнена за полиномиальное время. Более того, несмотря на то, что решения V отличаются от решении задачи V (поскольку некоторые переменные удалены), число решений в обеих задачах одинаково.
Доказательство того, что #-полиномиальность сохраняется не только конъюнктивными, но и диофантовыми формулами, намного сложнее, чем в случае задач распознавания. Предложение 13.2. Пусть Г — множество отношений, R — отношение из Г, a S — отношение, определяемое формулой 3xmR{xi,... ,хт). Тогда задача #CSP(r U {S}) сводима к задаче #CSP(r). Чтобы доказать предложение 13.2 и некоторые другие результаты данного параграфа, нам потребуется метод интерполяции, разработанный в работе [215]. Этот метод опирается на следующее утверждение.
Теорема 13.2. Пусть Гі,Г2 — множества отношений на конечном множестве такие, что Гт конечно и Ро! (Гі) С Рої (Г2). Тогда задача #СБР(Г2) сводима к задаче #СБР(Гі) за полиномиальное врелія. Следовательно, если задача CSP(ri) #-полиномиальна, то #СБР(Г2) также полиномиальна, и если #CSP(T2) #Р-полна, то задача #СБР(Гі) также #Р-полна.
Таким образом, как и в случае задач распознавания, вся информация о сложности задачи #CSP(F) может быть извлечена из множества полиморфизмов Г. В частности, результат [47, 48] о -полиномиальных булевых множествах отношений может быть переформулирован следующим образом. Предложение 13.3. Мнооюество булевых отношений Г -полиномиально тогда и только тогда, когда каждое отношение из Г инвариантно относительно операции х — у -f- z, где + ,— обозначают сложение и вычитание по модулю 2. В противном случае Г #Р-полно. Согласно теореме 13.2, если РоІ(Гі) = Pol (Г2) или, эквивалентно, Агх = Аг2, то множества ГьГ2 -полиномиальны или #Р-полны одновременно. Следовательно, как и в случае задач распознавания все задачи могут быть параметризованы конечными алгебрами таким образом, что задачи, соответствующие термально эквивалентным алгебрам, имеют одинаковую сложность. Алгебра A = (A;F) называется -полиномиальной \#Р-полной], если соответствующее множество отношений Inv(F) является -полиномиальным [#Р-полным]. Через #CSP(A) мы обозначаем задачу #CSP(lnvF).
Используя определение, данное выше, мы можем сформулировать проблему 2С следующим образом. Проблема 13.1 (Проблема классификации). Охарактеризовать -полиномиальные и #Р-полные конечные алгебры. Предложение 13.3 является первым шагом в решении этой проблемы, поскольку, будучи сформулированным в только что введенных терминах, оно дает следующую полную классификацию двухэлементных алгебр относительно сложности задачи о подсчете числа решений. Предложение 13.3 ([47, 48]). Двухэлементная алгебра А = ({0,1} ,F) #-полиномиальна тогда и только тогда, когда х — у + z (mod 2) является термальной операцией А. В противном случае А #Р-полна. Как и в случае задач распознавания, #-полиномиальность сохраняется основными алгебра-ческими операторами. Теорема 13.3. Пусть A = (A;F) — конечная алгебра. Тогда (і) если А -полиномиальна, то все ее подалгебры, все гомоморфные образы и все прямые степени такоюе -полиномиальны; (іі) если А имеет #Р-полиую подалгебру, #Р-полный гомоморфный образ или #Р-полную прямую степень, то А такоісе #Р-полна.
Рассмотрим частную задачу V — (V; А; С) задачи #CSP(r U {Ca а Є А}) и пусть V — частная задача (V ;A;C) задачи #CSP(ru{==4,-Ri})), где V = VU{va а Є A}, (va для а Є А есть переменная, не принадлежащая множеству V), а С содержит все ограничения С = (s, R) из С, для которых R Є Г. Кроме того, для каждого ограничения вида (v, {а}) из С, множество С содержит ограничение ((г ,ъ 0),=л), а также С содержит ограничение ({vai,... ,van),R\).
Число решений задачи V равно множеству решений ст задачи V , для которых справедливо равенство т"(гіа) = а при любом а Є А. Обозначим через Af множество таких решений. Мы вычислим мощность множества А/" в две стадии. На первой стадии мы вычисляем, сколько решений а задачи V присваивают переменным va, а є А, попарно различные решения. Множество таких решений обозначим через М. На второй стадии мы выражаем мощность множества N через мощность множества Л4.
Чтобы выполнить первую стадию, рассмотрим множество Part(yl) всех разбиений множества А и естественный порядок на Part(j4). Для разбиения 9 пусть 1(9) обозначает главный идеал, порожденный 9. Для каждого разбиения 9 Є Рагт(Л) через V g обозначим задачу (V ,A,C U {{(va,va ), =л) I aiа принадлежат одному и тому же классу в}). Отметим, что отображение а является решением задачи V e если а является решением V и для любых а, о из одного и того же класса 9 справедливо равенство a(va) = a(va ). Обозначим через No число решении задачи V g. Число No может быть найдено с помощью оракула #CSP(r), поскольку {=A,Rl}C{T).
Похожие диссертации на Алгебраические методы в исследовании комбинаторных задач
