Алгебраические методы в исследовании комбинаторных задач тема диссертации и автореферата по ВАК РФ 01.01.06, доктор физико-математических наук Булатов, Андрей Арнольдович

• Булатов, Андрей Арнольдович
• доктор физико-математических наук
• 2008

Оглавление диссертации доктор физико-математических наук Булатов, Андрей Арнольдович

Введение

В.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. NP-IГОлнoтa и гипотеза о дихотомии.

4.1. Ж/Чголные алгебры и результаты о дихотомии

4.2. Необходимое условие полиномиальности на языке теории ручных конгруэнций

4.3. Распознавание полиномиальных задач

§5. Полиномиальные алгебры: 2-полурешетки.

5.1. Вспомогательные наблюдения

5.2. Простые 2-полурешетки.

5.3. Общий случай.

§6. Полиномиальные алгебры: мальцевские алгебры

6.1. Строение подпрямых произведений алгебр с мальцевской операцией.

6.2. Задачи CSP с мальцевским полиморфизмом.

6.3. Подпрограммы и комментарии.

6.4. Два типа алгоритмов

§7. Результаты о дихотомии: строго простые алгебры.

§8. Результаты о дихотомии: З-элементные алгебры.

8.1. Полиномиальные множества отношений на 3-элементном множестве.

8.2. Алгоритмы для задач CSP на З-элемептпом множестве

8.3. Доказательство теоремы 8.

8.4. Практическое руководство к решению задач CSP на 3-элементном множестве

§9. Результаты о дихотомии: консервативные алгебры.

9.1. Схема доказательства.

9.2. Структура отношении из консервативных языков.

9.3. Двусвязные отношения

9.4. Связность, прямоугольность и разложения.

9.5. R/b-связные отношения.

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. Взвешенная задача CSP

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. Алгоритмы.

Введение диссертации (часть автореферата) на тему «Алгебраические методы в исследовании комбинаторных задач»

В.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"; ц немногочисленных русскоязычных работах по этой проблематике встречается также название "Обобщенная выполнимость".

2Такие формулы называются также примитивно позигпивпылш. баз данных [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, 110, 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 (для С++), 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 в заданную конечную модель TL. Для класса Г конечных моделей мы обозначаем через CSP(*, Г) множество всех частных задач CSP, в которых модель 72. принадлежит Г, а через СЭР(Г, *) — множество частных задач CSP, в которых Q принадлежит Г. Если Г одноэлементен, скажем, Г = {7£}, мы используем обозначение CSP(*,7£) и CSP(7£, *), соответственно. Возможны, разумеется, и комбинированные ограничения; соответствующие классы CSP будут обозначаться через CSP(ri,r2).

Исторически первыми изучались ограничения вида 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, 110, 156].

Изучение ограниченных задач CSP вида CSP(*,r) началось с пионерской работы Шефера [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 в 7?. [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(*, Г) с помощью некоторых логических формализмов. Говорят, что задача CSP(*,72.), где 'IZ — конечная модель, имеет ширину к, если класс моделей, не гомоморфных 1Z, может быть определен с помощью программы на языке Даталог, каждое правило которой содержит не более к переменных Поскольку выразимость в Даталоге влечет также выразимость на языке первого порядка с оператором неподвижной точки, каждая такая задача CSP может быть решена за полиномиальное время [3] Показано также, что проблема, имеет ли CSP(*,7?.) ширину 1, алгоритмически разрешима. Наконец, авторы построили широкий класс задач CSP, не имеющих конечной ширины. Все задачи из этого класса могут быть сведены к решению систем уравнений над конечной абелевой группой. Федер и Варди поставили задачу об описании конечных моделей TZ, для которых CSP(*,7?.) имеет конечную ширину, и предположили, что конечную ширину не имеют в точности те задачи, с помощью которых могут быть смоделированы системы уравнении над конечными абелевыми группами. В [55] Далмау охарактеризовал задачи вида CSP(*,7£), имеющие ширину 1.

Понятие задач ограниченной ширины естественно распространяется и па задачи вида CSP(7?.,*). Был получен ряд условий, эквивалентных конечности ширины [54, 152, 153, 155, 219]:

- класс CSP(*, TZ) [соответственно CSP(7£, *)] имеет ширину к- существует программа на Даталоге, распознающая, верно ли, что не существует гомоморфизма данной модели в TZ [гомоморфизма из И в данную модель), и имеющая не более к переменных в каждом правиле;

- класс моделей, для которых существует гомоморфизм данной модели в 1Z [гомоморфизм из 7Z в данную модель], выразим с помощью бесконечной экзистенциальной позитивной формулы, содержащей не более к переменных;

- для любой модели Q в игре на гомоморфизм с к фишками на паре Q, 'JZ [на паре TZ, О] (определение см. в разделе 1.4) существует выигрышная стратегия для дупликатора тогда и только тогда, когда существует гомоморфизм из Q в 1Z [гомоморфизм из 7Z в Q];

- 7Z обладает свойством древесной дуальности [обратной древесной дуальности] : для любой модели Q гомоморфизм из Q в К существует тогда и только тогда, когда каждая модель древесной ширины не более к, гомоморфная Q, гомоморфна также и 1Z [гомоморфизм из 71 в Q существует тогда и только тогда, когда каждая модель древесной ширины не более к, гомоморфная 7Z, гомоморфна также и О].

Наивысшим достижением, полученным в рамках логического подхода, является характе-' ризация полиномиальных задач вида СЭР(Г, *). В [117, 118] Гроэ и другие показали, что при некоторых допущениях из теории параметризованной сложности задача CSP(r, *) решаема за полиномиальное время тогда и только тогда, когда для некоторого к граф Гаифмана каждой модели из Г имеет древесную ширину, не превышающую к. В [117] Гроэ построил рекурсивный класс Г конечных моделей такой, что задача CSP(r,*) не является NP-полной и, если P^NP, не может быть решена за полиномиальное время. Для задач о подсчете числа решений Далмау показал [53], что #CSP(r,*) может быть решена за полиномиальное время тогда и только тогда, когда древесная ширина графов Гаифмана моделей из Г ограничена.

Однако в изучении задач вида CSP(*, Г) этот подход оказался значительно менее эффективным. Кроме упомянутой серии эквивалентных условий, внимания заслуживает лишь один результат. Он касается выразимости класса конечных моделей, не гомоморфных некоторой фиксированной модели 'R,, на языке первого порядка — отметим, что такая выразимость влечет полиномиальность задачи CSP(*,7?.). Атцериас в [12] доказал, что указанный класс выразим на языке первого порядка тогда и только тогда, когда 1Z обладает конечной дуальностью, т.е. существует конечное множество Д "запрещенных" конечных моделей такое, что модель Q не гомоморфна 7Z тогда и только тогда, когда какая-нибудь модель из Д гомоморфна 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], в которой доказывалось, что большинство комбинаторных задач из теории графов решается за полиномиальное время для графов ограниченной древесной ширины. Многие из этих результатов могут быть выведены из того факта, что задача CSP(F, *) решаема за полиномиальное время, если древесная ширина графов Гаифмана моделей из Г ограничена некоторым к [152]. С другой стороны, как мы увидим ниже, зачастую изучение частных комбинаторных задач служит источником идей для исследований по задаче CSP, а в некоторых случаях результаты, полученные для частных задач, имеют следствия, справедливые для общей задачи CSP. Мы остановимся лишь на тех комбинаторных задачах, взаимодействие которых с общей теорией CSP является особенно тесным.

Наиболее важной из таких задач является, безусловно, И-Раскраска графа. Многие постановки в этой области близки к проблемам, возникающим при изучении общей задачи CSP. Классификация сложности этой задачи для ориентированных графов повлекла бы за собой классификацию сложности задач CSP(*, TZ) для произвольных конечных моделей, как показывает упомянутый результат Федера и Варди [92]. Хелл и Нешетрил в [127] доказали, что для неориентированного графа Н задача Я-Раскраска графа (т.е. CSP(*,ii)) может быть решена за полиномиальное время тогда и только тогда, когда Н — двудольный граф, и NP-полна в противном случае. В случае ориентированных графов имеются частичные продвижения. В [120, 129) показано, что //"-Раскраска графа решаема за полиномиальное время, если Н путь. Федер [85] показал, что дихотомия "Р - Г\тР-полнота" справедлива в случае ориентированных циклов, однако, он не предложил критерия, различающего полиномиальный и ^-полный случаи. Отметим, что уже в случае ориентированных деревьев неизвестно, справедлива ли указанная дихотомия [128]. Банг-Йенсен, Хелл и МакДжилливрэй [19] показали, что если II содержит турнир в качестве подграфа, то Я"-Раскраска графа решаема за полиномиальное время тогда и только тогда, когда Я содержит не более одного ориентированного цикла. В [18] была сформулирована гипотеза о том, что это свойство является необходимым и достаточным для полиномиальное™ обсуждаемой задачи в случае, когда Н не содержит источников и стоков. Гипотеза была подтверждена в ряде частных случаев [18, 19, 20, 180, 181]. Любопытно, что во всех полиномиально разрешимых случаях полиномиальность может быть объяснена древесной дуальностью графа Я [128, 188].

Интенсивно изучались также некоторые варианты задачи Я-Раскраска графа, включая задачу Консервативная Я-раскраска графа (в которой требуется определить, существует ли гомоморфизм из данного графа в Я такой, что каждая вершина отображается в одну из вершин из заданного списка), а также соответствующие им задачи о подсчете числа решений (гомоморфизмов) #Я-Раскраска графа н Консервативная #Я-раскраска графа. В случае неориентированных графов имеется полная классификация для задачи Консервативная Я-раскраска графа [28, 86, 89, 90]; для задач #Я-Раскраскл графа и Консервативная #Я-раскраска графа такие классификации получены в [82] и [71, 73, 72], в обоих случаях критерий одинаков: задача может быть решена за полиномиальное время тогда и только тогда, когда каждая компонента связности Я — полный двудольный граф или полный граф со всеми петлями. Все упомянутые проблемы изучались также и в случае, когда в качестве исходных рассматриваются лишь графы из определенных классов, например, планарные графы или графы с ограниченными степенями вершин [70, 71, 73, 80, 82, 86, 103, 123, 181, 189].

Для некоторых задач из теории графов дихотомия "Р - NP-пoлнoтa", по всей видимости, не имеет места. Так, в [91] было предложено записывать многие задачи из теории графов на языке так называемых консервативных разбиений. Этот формализм выразим в терминах задачи СЭР, хотя и не в виде СЗР(*, Г). Однако соответствующая задача во многих случаях может быть сведена к достаточно длинной (псевдополиномиальной) серии задач СЭР и — в случае, когда полученные задачи решаемы за полиномиальное время, — может быть решена за субэкспоненциальное время. Этот результат дает достаточно эффективные алгоритмы для многих задач из теории графов, о которых неизвестно, что они ИР-полны, но неизвестен также и полиномиальный алгоритм. Далее, в [87] получена полная классификация задач о консервативных разбиениях, решаемых за псевдополипомиальное время. Наконец, в [88] эти результаты были обощены на случай общей задачи СЭР.

Несмотря на достигнутые продвижения, основной трудностью, с которой сталкивается дискретно-математический подход, является недостаточность языка теории графов для описания свойств графов, определяющих сложность соответствующих задач. Так, результаты работ [28, 86, 89, 90] используют довольно громоздкие и не всегда прозрачные конструкции, а результаты из [87, 88] используют язык полиморфизмов, описанный в следующем разделе, их представление в теоретико-графовых терминах неизвестно.

В.2.5 Алгебраический подход

Этот подход к изучению задач вида CSP(*,r) был предложен Джевонсом и его соавторами в [137, 142]. Он основан на использовании алгебраических свойств моделей из Г. Операция (возможно, многоместная) на основном множестве модели 72. называется полиморфизмом 72, если она сохраняет все отношения этой модели. Джевонс доказал, что для любых конечных моделей 72] и 7?.2 если каждый полиморфизм 72 j является также полиморфизмом 72т, то CSР(72.0) сводится за полиномиальное время к CSP(72.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. имеет лишь неконстантные унарные полиморфизмы, то задача CS Р (*, 72.) NP-полна. Это имеет место, например, в случае полных графов и, следовательно, применительно к задаче fc-packpacka графа.

В случае задач о подсчете числа решений полиморфизмы также играют заметную роль. В частности, можно проверить, что теорема о дихотомии из [47] может быть сформулирована следующим образом. В случае, когда 72. — двухэлементная модель с основным множеством, например, {0,1}, задача #CSP(*,72.) может быть решена за полиномиальное время тогда и только тогда, когда операция х — у л (mod 2) является полиморфизмом 72; в противном случае эта задача #Р-полна.

Полиморфизмы были использованы в [51] при попытке охарактеризовать задачи CSP, решаемые с недетерминированной логарифмической памятью. В [139] показано, что если модель 72. имеет к-местную функцию единогласия, то CSP(*, 72) имеет ширину к— 1. Наконец, в [36, 55] были введены понятия более общие, чем полиморфизмы. В первой из этих статей с помощью полиморфизмов удалось охарактеризовать задачи CSP ширины 1, а во второй — задачи CSP, решаемые с помощью некоторого специального алгоритма.

4Применением недавнего результата Рейнгольда [196] о том, что задача Достижимость в неориентированном графе может быть решена с логарифмической памятью, сводимость в этой теореме может быть ослаблена до сводимости с логарифмической памятью.

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

При внимательном рассмотрении логического и дискретно-математического подходов к изучению ограниченных задач CSP становится ясно, что при их использовании возникают значительные трудности, связанные с недостаточной выразимостью соответствующих языков. Это позволяет заключить, что, по-видимому, ресурс этих подходов к настоящему времени в известной мере исчерпан. Что касается алгебраического подхода, то его выразительные возможности выглядят более адекватными поставленным задачам. Трудности применения этого подхода связаны с огромным разнообразием возможных полиморфизмов. Однако до последнего времени не были использованы мощные методы изучения алгебраических операций, разработанные в современной универсальной алгебре. Поэтому представляется особенно актуальным привлечение для изучения задачи CSP методов и результатов универсальной алгебры.

Основная цель диссертации состоит в систематическом развитии алгебраического подхода к исследованию задачи CSP, а также применении разработанных методов к изучению сложности ограниченных задач CSP и задач, с ними связанных. Мы выделим несколько более конкретных целей.

A. Развитие разделов универсальной алгебры, изучающих строение алгебр с точностью до термальной эквивалентности. Как станет ясно, особую роль здесь играет изучение локальной структуры идемпотентных алгебр, а также свойств идемпотентных алгебр, которые могут быть выведены из особенностей их локального строения.

Б. Использование алгебраического подхода для систематического изучения сложности ограниченных задач CSP, вплоть до исчерпывающего описания задач, решаемых за полиномиальное время.

B. Использование алгебраического подхода для систематического изучения сложности ограниченных задач о подсчете числа решений, вплоть до исчерпывающего описания задач, решаемых за полиномиальное время.

Г. Применение разработанных методов и полученных результатов для исследования проблем дискретной математики и теоретической информатики, связанных с различными типами задач CSP.

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

В этом разделе мы сформулируем основные проблемы, рассматриваемые в диссертации.

В 1978 году Шефер [203] охарактеризовал все полиномиальные подзадачи Булева выполнимость, т.е. все классы Г двухэлементных моделей такие, что задача CSP(*,r) полиномиальна. В той же работе им была поставлена аналогичная проблема для классов произвольных конечных моделей.

Проблема 1С (Проблема классификации). Охарактеризовать классы Г конечных моделей такие, что задача СЗР(*,Г) полиномиальна [АгР-полна].

Из результата Шефера следует также, что для каждого класса двухэлементных моделей соответствующая задача либо полиномиальна, либо NP-полна. Этот факт априори далеко не очевиден, поскольку между классами Р и ИР существует бесконечно много различных классов сложности. Как упоминалось выше, Федер и Варди в [92] поставили проблему, верна ли такая дихотомия для произвольных конечных моделей.

Проблема Ю (Проблема дихотомии). Выяснить, верно ли, что для любого класса Г конечных моделей задача С8Р(*, Г) либо полиномиальна, либо ЫР-полна.

Для приложений важно иметь метод, позволяющий распознавать, когда задача СБР(*,Г) полиномиальна. Так как решение проблемы классификации само по себе может не обеспечить такой метод, актуальной является следующая

Проблема 1М (Проблема распознавания). Найти эффективный алгоритм, определяющий по данному классу Г конечных моделей, является ли задача С8Р(*,Г) полиномиальной.

Вероятнее всего, решение проблемы классификации обеспечит также и алгоритмы, решающие задачи С8Р(*, Г) тогда, когда они полиномиальны. Однако даже в этом случае найденные алгоритмы могут не быть максимально эффективными, например, в силу своей общности. Поэтому разработка алгоритмов, решающих полиномиальные задачи С8Р(*, Г), является проблемой, заслуживающей особого внимания.

Проблема 1А (Проблема разработки алгоритмов). Разработать эффективные алгоритмы, решающие задачи вида СЭР(*,Г) в тех случаях, когда они полиномиальны.

Отметим, что для случая, когда Г — множество 2-элементных моделей, результаты работы [203] полностью решают проблемы 1С,Ш. Все алгоритмы, необходимые для решения проблемы 1А в этом случае, были известны ранее (см. [104]). Наконец, проблема 1М в этом случае полностью решена в [154].

В статье [92] Федер и Варди отметили, что почти во всех известных случаях ограниченная задача С5Р может быть решена с помощью "локальных" методов (в самой статье в качестве такого метода использовались программы на Даталоге). Известны также примеры задач, которые могут быть решены за полиномиальное время, но не могут быть решены локальными методами. Поскольку локальные методы являются наиболее широко распространенными при практическом решении задач СЭР, следующая проблема представляет значительный интерес.

Проблема Ь (Проблема локальных методов). Охарактеризовать классы Г конечных моделей такие, что задача СБР(*, Г) может быть решена с помощью локальных методов.

В [47] (см. также [48]) Кренью и Херрман выполнили работу, аналогичную работе Шефера [203] для задач о подсчете числа решений. Это подсказывает, что для задач о подсчете числа решений могут быть сформулированы проблемы, аналогичные проблемам 1С, Ш, 1М, 1А.

Проблема 2С (Проблема классификации). Охарактеризовать классы Г конечных моделей такие, что задача #С8Р(*, Г) решаема за полиномиальное время [#Р-полна].

Проблема 20 (Проблема дихотомии). Выяснить, верно ли, что для любого класса Г конечных моделей задача #С8Р(*,Г) либо полиномиальна, либо #Р-полна.

Проблема 2М (Проблема распознавания). Найти эффективный алгоритм, определяющий по данному классу Г конечных моделей, решаема ли задача #С8Р(*, Г) за полиномиальное время.

Проблема 2А (Проблема разработки алгоритмов). Разработать эффективные алгоритмы, решающие задачи вида #СЗР(+,Г) в тех случаях, когда могут быть решены за полиномиальное врелгя.

Третий блок проблем, рассматриваемых в диссертации, относится к методам изучения задач СЭР. Как было упомянуто выше, мы концентрируем внимание на использовании методов универсальной алгебры для изучения задач СЭР. Однако наиболее мощные из этих методов, такие, как теория ручных конгруэнций [131] и теория коммутаторов [96], имеют дело со структурой алгебр с точностью до полиномиальной эквивалентности, в то время как проблемы, сформулированные выше, требуют использования лишь термальных операций универсальных алгебр. Поэтому насущной представляется

Проблема Т. Развить методы исследования универсальных алгебр с точностью до термальной эквивалентности.

Проблема Т сформулирована весьма широко, однако позже мы уточним, какие аспекты этой проблемы наиболее важны для изучения задач СЭР.

Оказалось, что для изучения задач о подсчете решений необходимо глубокое понимание структуры конечных мальцевских алгебр. Мальцевские алгебры были предметом интенсивных исследований на протяжении многих лет, см., например, [16, 34, 49, 119, 200, 202], а также монографию [207]. Однако в нашем случае необходим ряд свойств подалгеб прямых степеней мальцевских алгебр с точки зрения их локальной структуры.

Проблема Б. Изучить локальную структуру подпрямых произведений мальцевских алгебр.

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

В диссертации решены проблемы 2С, 20, 2А в полном объеме; проблемы 1С, Ш, 1М, 1А, Ь решены в обширных частных случаях (для 3-элементных моделей, консервативных моделей и моделей, клон полиморфизмов которых минимален); проблема 1М решена в общем случае — при условии, что верна наша гипотеза, касающаяся проблемы 1С; получены существенные продвижения в решении проблем Т и Э; проблема 2М осталась нерешенной. В таблице 1 для каждой из этих проблем указаны теоремы, которые дают ее решение (для проблем 1С, Ш, 1М, 1А, Ь в указанных частных случаях) или продвижения. Частичное решение проблемы 1А дано

Проблемы 1C.1D 1М L 2C,2D

Теоремы 7.1,8.1, 9.1, 12.1 4.3 11.1, 11.2, 11.3 15.1

Таблица 1 алгоритмами, представленными в разделах 6.2, 8.2 и 9.6; решение проблемы 2А дано алгоритмом, представленным в разделе 15.4. Результаты, касающиеся изучения структуры конечных алгебр с точностью до термальных операций (проблема Т) содержатся в предложениях 10.110.6 и 11 1; результаты относительно структуры конечных мальцевских алгебр (проблема S) — в предложении 6.3 и леммах 6.3-6.7

Отметим, чго для обоих типов задач СЭР (распознавания и о подсчете решений) решения проблем 1С и Ш, а также проблем 2С и 2Б даются одними и теми же теоремами. Ясно, что причина этого состоит в том, что для этих классов задач в изученных случаях справедлива дихотомия "Р - ЫР-полнота" [соответственно, 'ТР - #Р-полнота"). Однако, такого рода дихотомия и, следовательно, одновременное решение проблем 1С, Ш [проблем 2С, 2Б] имеет место далеко не всегда; например, в [117) получено описание всех полиномиально разрешимых задач вида С8Р(Г,*) и, вместе с тем, продемонстрирован класс Г, для которого С8Р(Г,*) не NP-полна, но и не может быть решена за полиномиальное время (если Р^КР).

Как уже объявлено в разделе В.З, основополагающей идеей диссертации является использование универсальной алгебры для изучения задачи СЭР. Прежде всего, мы показываем, что методы универсальной алгебры являются, по-видимому, наиболее адекватными для этой цели. Имевшиеся алгебраические результаты были недостаточными для изучения задачи СЭР. В частности, как отмечено в предыдущем разделе, соответствующие алгоритмы требуют знания структуры конечных алгебр с точностью до термальной эквивалентности. Пополняя запас необходимых инструментов, мы показываем, что для каждой конечной алгебры такой, что многообразие, ею порожденное, избегает тип 1 в смысле теории ручных конгруэнции5, существует ее редукт, подалгебры которого образуют связный гиперграф, и многообразие, порожденное редуктом, имеет то же множество типов, в частности, избегает тип 1. Более того, даже если ограничиться подалгебрами очень простого вида — двухэлементными и изоморфными аффинной алгебре по модулю некоторой конгруэнции, — мы получим связный гиперграф. Далее, мы показываем, что операции указанных подалгебр могут быть продолжены до термальных операций исходной алгебры весьма регулярным образом. Набор возможных видов подалгебр отражает локальное строение алгебры, а получившийся гиперграф — ее глобальное строение. Найденные СЗР-алгоритмы используют простые алгоритмы, работающие для подалгебр вышеуказанного ограниченного типа, и гиперграф алгебры — для того чтобы решить задачу СБР на всей алгебре.

Как станет ясно, для решения задач о подсчете решений необходима более детальная информация о строении мальцевских алгебр. Полученные в диссертации результаты показывают, что подпрямые произведения мальцевских алгебр обладают свойствами, сходными со свойством прямоугольности, более или менее сильными в зависимости от того, избегает ли алгебра тип 2. В критерии полиномиальности для задач о подсчете решений, теореме 15.1, мы используем новое условие на конгруэнции конечных алгебр в многообразии — конгруэнц-сингулярность. Это условие близко к условию регулярности конгруэнции, изучавшемуся ранее [96). Конгруэнц-сингулярные многообразия уже встретили заинтересованное внимание специалистов по универсальной алгебре.

Определения типов, фигурирующих в этой теории, приведены в разделе 2.3.

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

В доказательствах полученных в диссертации результатов используется широкий спектр методов. В соответствии с тем, что все результаты можно условно разделить на три большие группы — результаты о строении универсальных алгебр, доказательства трудности комбинаторных задач и построение полиномиальных алгоритмов, — в используемых методах можно выделить три типа.

• Собственно универсально-алгебраические методы, включающие методы теории решеток, теории коммутаторов и теории ручных конгруэнций.

• Методы теории сложности, т.е. сводимости различных видов, таких, как полиномиальная сводимость по Карпу, сводимость по Тьюрингу, сводимость с логарифмической памятью. Иногда нам приходится пользоваться некоторыми приемами полиномиальной арифметики и комплексного анализа. Отметим также, что часть сводимостеп получена с использованием универсально-алгебраических результатов см., например, теорему 13.6.

• Использование алгебраических понятий и фактов для построения комбинаторных алгоритмов. Типичным примером является использование условий из теории коммутаторов и теории ручных конгруэнций для построения алгоритмов для решения задач CSP распознавания над мальцевскими алгебрами и алгоритма для решения задач о подсчете решений.

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

Диссертация, кроме введения, имеет три главы (имеющие номера с 0 по 2), а также список литературы. Главы делятся на параграфы, имеющие сквозную нумерацию. Почти все параграфы делятся на пункты, нумеруемые двумя индексами, первый из которых означает номер параграфа. В некоторых случаях используется деление на подпункты, нумеруемые тремя индексами. В пунктах, на которые делится введение, роль первого индекса играет буква "В".

Охарактеризуем вкратце содержание каждой из глав. В главе 0 собрана вспомогательная информация, необходима для доказательства основных результатов диссертации. Глава 1 посвящена результатам о задачах распознавания CSP, а глава 2 задачам CSP о подсчете решений.

Результаты всех типов, также примеры и рисунки, имеют двухиндексную нумерацию, в которой первый индекс означает номер параграфа. Как и номерах пунктов, роль первого индекса во введении играет буква "В".

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

Результаты диссертации были представлены на международных симпозиумах по автоматам, языкам и программированию (Женева, 2000; Турку, 2004), симпозиуме по теории вычислений (Херсонисос, 2001), международной летней школе по общей алгебре и упорядоченным множествам (Стржебске Плезо, 2001), международных конференциях по основам компьютерных наук (Ванкувер, 2002; Бостон, 2003), международной конференции по полугруппам, автоматам и языкам (Коимбра, 2002), международной конференции по универсальной алгебре и теории решеток (Нэшвнлл, 2002), международной конференции по алгебре (Лиссабон, 2003), международной конференции по искусственному интеллекту (Акапулько, 2003), международных симпозиумах по логике в компьютерных науках (Оттава, 2003; Турку, 2004), международной конференции по теории и практике задач СЭР (Кинсале, 2003), международной школе по раскраскам графов (Дагштуль, 2003), международных школах по задачам СЭР (Монреаль, 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,

230, 231, 233, 234, 236, 237, 241, 242, 243, 249, 250] являются совместными. В статьях [241, 230,

231, 233], а также тезисах конференций [228, 233[, автору принадлежит подавляющая часть доказательств. В работе [250] и соответствующих тезисах конференций [236] автору принадлежат доказательства всех результатов, исключая сведение к случаю идемпотентных алгебр. Статьи [234, 242] являются обзорами, в статье [229] автору принадлежит результат о полино-мпальностн алгебр с минимальным клоном термальных операций, порожденным операцией консервативного коммутативного группоида. Заметим, что результаты этой статьи были значительно обобщены в [239]. В статье [249] приводится упрощенная, хотя и менее мощная, версия алгоритма из [245]; эта статья написана в нераздельном соавторстве с В. Далмау. Работа тезисы на конференциях [237]) написана в нераздельном соавторстве с М. Гроэ.

Работы [251]-[256] содержат результаты, тесно связанные с темой диссертации, по не вошедшие в текст диссертации.

Автор считает приятным долгом выразить глубокую благодарность Льву Наумовичу Шев-рину за постоянное стимулирующее внимание и всестороннюю поддержку. С благодарным чувством я вспоминаю своего первого учителя Евгения Витальевича Суханова, многолетнее сотрудничество с которым сыграло неоценимую роль в моем научном становлении. Я благодарен П. Джевонсу, который в свое время привлек мое внимание к задачам СБР, за продолжительное и плодотворное сотрудничество, а также М. В. Волкову, В. Б. Репнпцкому и другим участникам руководимого Л. II. Шевриным семинара "Алгебраические системы" за многочисленные полезные обсуждения, в немалой степени способствовавшие исследованиям, отраженным в диссертации.

Глава О

Базисные понятия и факты

§1 Задача СЭР

Список литературы диссертационного исследования доктор физико-математических наук Булатов, Андрей Арнольдович, 2008 год

1. В.Г. Боднарчук, J1.A. Калужнин, В.Н. Котов, and Б.А. Ромов. Теория Галуа для алгебр Поста. I // Кибернетика. 1969. Т.З. С. 1-10.

2. В.Г. Боднарчук, J1.A. Калужнин, В.Н. Котов, and Б.А. Ромов. Теория Галуа для алгебр Поста. II // Кибернетика. 1969. Т.5. С.1-9.

3. F. Afrati, S.S. Cosmadakis, and М. Yannakakis. On Datalog vs. polynomial time 11 Proc. of 10th ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems (Denver 1991). ACM Press. 1991. P. 13-25.

4. J.F. Allen. Maintaining knowledge about temporal intervals // Communications of the ACM. 1983. Vol. 26. P. 832-843.

5. J.F. Allen. Natural Language Understanding. NY:Benjamin Cummihgs, 1994.

6. S. Arnborg. Efficient algorithms for combinatorial problems on graphs with bounded decomposability // BIT. 1985. Vol. 25. P. 2-23.

7. S. Arnborg, D.G. Corneil, and A. Proskurowski. Complexity of finding an embedding in k-trees // SIAM J. of Algebraic and Discrete Methods. 1987. Vol. 8. P. 277-284.

8. S. Arnborg, S. Hedetniemi, and A. Proskurowski, ed. Efficient algorithms and partial /c-trees. Amsterdam: North-Holland Publishing Co. 1994.

9. S. Arnborg, J. Lagergren, and D. Seese. Easy problems for tree-decomposable graphs // J. Algorithms. 1991. Vol. 12, №2. P. 308-340.

10. S. Arnborg and A. Proskurowski. Linear time algorithms for NP-hard problems restricted to partial k-trees // Discr. Appl. Math. 1989. Vol. 23, №1. P. 11-24.

11. B. Aspvall, M.F. Plass, and R.E. Tarjan. A linear time algorithm for testing the truth of certain quantified Boolean formulas // Information Processing Letters. 1979. Vol. 8. P. 121—123.

12. A. Atserias. On digraph coloring problems and treewidth duality // Proc. of the 20th Annual IEEE Simp, on Logic in Computer Science (Chicago, 2005). IEEE Computer Society Press. P. 106-115.

13. F. Bacchus and A. Grove. On the forward checking algorithm // Lecture Notes in Computer Science. 1995. Vol. 976. P. 292-309.

14. F. Bacchus and van Run, P. Dynamic variable ordering in CSPs // Lecture Notes in Computer Science. 1995. Vol. 976. P. 258-277.

15. K.A. Baker and A.F. Pixley. Polynomial interpolation and the Chinese remainder theorem // Mathematische Zeitschrift. 1975. Vol. 143. P. 165-174.

16. J. Bang-Jensen and P. Hell. The effect of two cycles on the complexity of colourings by directed graphs 11 Discr. Appl. Math. 1990. Vol. 26, №1. P. 1-23.

17. J. Bang-Jensen, P. Hell, and G. MacGillivray. The complexity of colourings by semicomplete digraphs 11 SIAM J. of Discr. Math. 1988. Vol.1. P. 281-289.

18. J. Bang-Jensen, P. Hell, and G. MacGillivray. Hereditarily hard H-coloring problems // Discr. Math. 1995. Vol. 138. P. 75-92.

19. C. Beeri, R. Fagin, D. Maier, A.O. Mendelzon, and J.D. Ullman. Properties of acyclic database schemes 11 Proc. of the 13rd Annual ACM Symp. on Theory of Computing. 1981. P. 355-362.

20. C. Beeri, Ft. Fagin, D. Maier, and M. Yannakakis. On the desirability of acyclic database schemes // J. ACM. 1983. Vol. 30. P. 479-513.

21. J.D. Berman, E.W. Kiss, P. Proehle, and A. Szendrei. The set of types of a finitely generated variety // Discr. Math. 1993. Vol. 112, №1-3. P. 1-20.

22. C. Bessiere and J-C. Regin. Arc consistency for general constraint networks: preliminary results // Proc. of IJCAI'97 (Nagoya, 1997). P. 398-404.

23. S. Bistarelli, U. Montanari, and F. Rossi. Semiring-based constraint solving and optimisation // J. ACM. 1997. Vol. 44. P. 201-236.

24. H. Bodlaender. Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees // J. Algorithms. 1990. Vol. 11, №4. P. 631-643.

25. Hans L. Bodlaender. Dynamic programming on graphs with bounded treewidth // Lecture Notes in Comput. Sci. 1988. Vol. 317. P. 105-118.

26. R.C. Brewster, T. Feder, P. Hell, J. Huang, and G. MacGillivray. Near-unanimity functions and varieties of graphs 11 Manuscript, 2003.

27. G.R. Brightwell and P. Winkler. Graph homomorphisms and phase transitions //J. Comb. Theory, Ser. B. 1999. Vol. 77. P. 221-262.

28. G.R. Brightwell and P. Winkler. Gibbs measure and dismantable graphs // J. Comb. Theory, Ser. B. 2000. Vol. 78. P. 141-166.

29. R. Bubley, M. Dyer, C. Greenhill, and M. Jerrum. On approximately counting colourings of small degree graphs // SIAM J. Comput. 1999. Vol. 29. P. 387-400.

30. R. Burton and J. Steif. Nonuniqueness of measures of maximal entropy for subshifts of finite type // Ergodic Theory and Dynamical Systems. 1994. Vol. 14. P. 213-236.

31. V. Chandru and J.N. Hooker. Extended Horn sets in propositional logic // J. ACM. 1991. Vol. 38. P. 205-221.

32. H. Chen and V. Dalmau. (Smart) look-ahead arc consistency and the pursuit of CSP tractability // Proc. 10th Int. Conf. on Principles and Practice of Constraint Programming (Toronto, 2004). Berlin:Springer-Verlag. 2004. P. 182-196. (LNCS, Vol. 3258).

33. D.A. Cohen, P.G. Jeavons, P. Jonsson, and M. Koubarakis. Building tractable disjunctive constraints // J. ACM. 2000. Vol. 47. P. 826-853.

34. D.A. Cohen, P.G. Jeavons, and M. Koubarakis. Tractable disjunctive constraints // Proc. 3rd Int. Conf. on Constraint Programming (Linz, 1997). Berlin:Springer-Verlag. 1997. P. 478-490. (LNCS, Vol. 1330).

35. P.G. Cohen, D.A. Jeavons and M. Gyssens. A structural decomposition for hypergraphs // Contemp. Math. 1994. Vol. 178. P. 161-177.

36. A.G. Cohn. Qualitative spatial representation and reasoning techniques // Berlin:Springer-Verlag. 1997. LNCS. Vol. 1303. P. 1-30.

37. S.A. Cook. The complexity of theorem-proving procedures // Proc. 3rd IEEE Symp. on the Foundations of Computer Sci. 1971. P. 151-158.

38. M.C. Cooper. An optimal k-consistency algorithm // Artificial Intelligence. 1989. Vol. 41. P. 89-95.

39. M.C. Cooper, D.A. Cohen, and P.G. Jeavons. Characterising tractable constraints // Artificial Intelligence. 1994. Vol. 65. P. 347-361.

40. B. Courcelle. Graph rewriting: An algebraic and logic approach // Handbook of Theoretical Computer Science. Amsterdam:Elsevier Science Publishers. 1990. P. 194-242.

41. B. Courcelle. The monadic second-order logic of graphs. III. Tree-decompositions, minors and complexity issues // RAIRO Theor. Informat. and Appl. 1992. Vol. 26, №3. P. 257-286.

42. B. Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs U Information and Computation. 1990. Vol. 85, №1. P. 12-75.

43. N. Creignou and M. Hermann. Complexity of generalized satisfiability counting problems // Information and Computation. 1996. Vol. 125, №1. P. 1-12.

44. N. Creignou, S. Khanna, and M. Sudan. Complexity Classifications of Boolean Constraint Satisfaction Problems. SIAM. 2001. (SIAM Monographs on Discrete Mathematics and Applications. Vol. 7).

45. G. Czedli and J. D. H. Smith. On the uniqueness of Mal'cev polynomials // Finite algebra and multiple-valued logic. Amsterdam:North-Holland. 1981. P. 127-145. (Colloq. Math. Soc. Janos Bolyai. Vol.28).

46. V. Dalraau. A new tractable class of constraint satisfaction problems // Proc. 6th Int. Symp. on Artificial Intelligence and Math. 2000. P. 1-6.

47. V. Dalmau. Constraint satisfaction problems in non-deterministic logarithmic space // Proc. 29th Int. Colloq. on Automata, Languages and Programming. Berlln:Springer-Verlag. 2002. P. 414-425. (LNCS, Vol. 2380).

48. V. Dalmau. Computational Complexity of Problems over Generalised Formulas. PhD thesis. Universität Politécnica de Catalunya. Barcelona. 2000.

49. V. Dalmau and P. Jonsson. The complexity of counting homomorphisms seen from the other side // Theor. Comput. Sei. 2004. Vol. 329, №1-3. P. 315-323.

50. A. Davenport, E. Tsang, C-J. Wang, and K. Zhu. GENET: A connectionist architecture for solving constraint satisfaction problems by iterative improvement // Proc. of AAAI'94. AAAI. 1994. P. 325-330.

51. R. Dechter. Enhancement schemes for constraint processing: Backjumping, learning and cutset decomposition // Artificial Intelligence. 1990. Vol. 41, №3. P. 273-312.

52. R. Dechter. Constraint networks // Encyclopedia of Artificial Intelligence. NY:Wiley. 1992. P. 276-285.

53. R. Dechter. From local to global consistency Artificial Intelligence. 1992. Vol. 55, №1. P. 87-107.

54. R. Dechter. Constraint processing. Morgan Kaufmann Publishers, 2003.

55. R. Dechter and A. Dechter. Structure-driven algorithms for truth maintenance // Artificial Intelligence. 1996. Vol. 82, №1-2. P. 1-20.

56. R. Dechter and I. Meiri. Experimental evaluation of preprocessing algorithms for constraint satisfaction problems // Artificial Intelligence. 1994. Vol. 68. P. 211-241.

57. R. Dechter, I. Meiri, and J. Pearl. Temporal constraint networks // Artificial Intelligence.1991. Vol. 49. P. 61-95.

58. R. Dechter and J. Pearl. Network-based heuristics for constraint satisfaction problems ¡j Artificial Intelligence. 1988. Vol. 34, №1. P. 1-38.

59. R. Dechter and J. Pearl. Tree clustering for constraint networks // Artificial Intelligence. 1989. Vol. 38. P. 353-366.

60. R. Dechter and J. Pearl. Structure identification in relational data // Artificial Intelligence.1992. Vol. 58. P. 237-270.

61. R. Dechter and P. van Beek. Local and global relational consistency // Theor. Comput. Sei. 1997. Vol. 173, №1. P. 283-308.

62. L. Denenberg and H. R. Lewis. The complexity of the satisfiability problem for Krom formulas // Theor. Comput. Sei. 1984. Vol. 30. P. 319-341.

63. Y. Deville, O. Barette, and P. van Hentenryck. Constraint satisfaction over connected row convex constraints // Proc. IJCAI'97. 1997. P. 405-411.

64. J. Diaz, M. Serna, and D.M. Thilikos. The complexity of parametrized H-colorings: A survey II Discr. Math.

65. J. Diaz, M. Serna, and D.M. Thilikos. The complexity of restrictive H-coloring // Discr. Appl. Math. 2005. Vol. 145. №2. P. 297-305.

66. J. Diaz, M. Serna, and D.M. Thilikos. Counting list H-colorings and variants // Technical Report LSI-01-27-R, Universität Politécnica de Catalunya, 2001.

67. J. Diaz, M. Serna, and D.M. Thilikos. Counting h-colorings of partial k-trees // Theor. Comput. Sei. 2002. Vol. 281. P.291-309.

68. Q. Donner. On the number of list h-colorings J. Graph Theory. 1992. Vol. 16, №3. P. 239-245.

69. T. Drakengren and P. Jonsson. Eight maximal tractable subclasses of Allen's algebra with metric time // J. Artificial Intelligence. 1997. Vol. 7. P. 25-45.

70. T. Drakengren and P. Jonsson. Reasoning about set constraints applied to tractable inference in intuitionistic logic //J. Log. Comput. 1998. Vol. 8. №6. P. 855-875.

71. O. Dubois and G. Dequen. A backbone-search heuristic for efficient solving of hard 3-SAT formulae // Proc. It. Joint Conf. on Artificial Intelligence. 2001. P. 248-253.

72. M. Dyer, A. Frieze, and M. Jerrum. On counting independent sets in sparse graphs // SIAM J. Comput. 2002. Vol. 31. P. 1527-1541.

73. M. Dyer and C. Greenhill. The complexity of counting graph homomorphisms Random Structures and Algorithms. 2000. Vol. 17. P. 260-289.

74. R. Fagin. Degrees of acyclicity for hypergraphs and relational database schemes // J. ACM. 1983. Vol. 30. P. 514-550.

75. T. Feder. Constraint satisfaction on finite groups with near subgroups // ECCC Technical Report. 2005. TR05-005.

76. T. Feder. Classification of homomorphisms to oriented cycles and of k-partite satisfiability // SIAM J. Discr. Math. 2001. Vol. 14, №4. P. 471-480.

77. S.W. Golomb and L.D. Baumert. Backtrack programming // J. ACM. 1965. Vol. 12, №4. P. 516-524.

78. G. Gottlob, L. Leone, and F. Scarcello. Hypertree decompositions and tractable queries 11 Proc. 18th ACM-SIGACT-SIGART Symp. on Principles of Database Systems (Philadelphia, 1999). P. 21-32.

79. G. Gottlob, L. Leone, and F. Scarcello. A comparison of structural CSP decomposition methods // Artificial Intelligence. 2000. Vol. 124, №2. P. 243-282.

80. G. Gottlob, L. Leone, and F. Scarcello. Hypertree decompositions; A survey // Proc. 26th Int. Symp. on Math. Foundations of Comput. Sei. Berlin.-Springer-Verlag. 2001. P. 37-57. (LNCS, Vol. 2136).

81. G. Gottlob, L. Leone, and F. Scarcello. Hypertree decomposition and tractable queries // J. Comput. Syst. Sei. 2002. Vol. 64, №3. P. 579-627.

82. G. Gottlob, N. Leone, and F. Scarcello. The compleonty of acyclic conjunctive queries // Proc. 39th Annual Symp. on Foundations of Comput. Sei. 1998. P. 706-715.

83. G. Gottlob, N. Leone, and F. Scarcello. Hypertree decompositions and tractable queries // Proc. 18th Symp. on Principles of Database Systems. 1999. P. 21-32.

84. D. Granot and D. Skorin-Kapov. On some optimization problems on k-trees and partial k-trees // Discr. Appl. Math. 1994. Vol. 48, №2. P. 129-145.

85. C. Greenhill. The complexity of counting colourings and independent sets in sparse graphs and hypergraphs Computational Complexity. 2000. Vol. 9. P. 52-73.

86. M. Grohe. The compleonty of homomorphism and constraint satisfaction problems seen from the other side // Proc. 44th Ann. Symp. Foundations of Computer Science (Cambridge, 2003). IEEE Computer Society. 2003. P. 552-561.

87. M. Grohe, T. Schwentick, and L. Segoufin. When is the evaluation of conjunctive queries tractable? // Proc. 33rd Annual ACM Symp. Theory of Computing (Hersonissos, 2001). ACM Press. 2001. P. 657-666.

88. H. Peter Gumm. Is there a Mal'cev theory for single algebras? // Algebra Universalis. 1978. Vol. 8, №3. P. 320-329.

89. W. Gutjahr, E. Welzl, and G. Woeginger. Polynomial graph colorings // Discr. Appl. Math. 1992. Vol. 35. P. 29-45.

90. M. Gysssens and J. Paradaens. A decomposition methodology for cyclic databases // Advances in Database Theory. NY:Plenum Press. 1984. Vol. 2. P. 85-122.

91. J. Hagemann and A. Mitschke. On n-permutable congruences // Algebra Universalis. 1973. Vol. 3. P. 8-12.

92. R. Haggkvist and P. Hell. Universality of a-mote graphs // Europian J. Combinatorics. 1993. Vol. 14. P. 23-27.

93. W.S. Havens and M. Vernooy. An evaluation of probabilistic value-ordering heuristics // Proc. Conf. on Artificial Intelligence. Berlin:Springer-Verlag. 1999. P. 552-561.

94. P. Hell. Algorithmic aspects of graph homomorphisms // Survey in Combinatorics 2003. Cambridge University Press. 2003. P. 239-276. (London Math. Soc. Lect. Note Ser., Vol. 307).

95. P. Hell and NeSetnl. Graphs and homomorphisms. Oxford University Press, 2004. (Oxford Lect. Ser. in Math, and its Applications. Vol. 28).

96. P. Hell and X. Zhu. Homomorphisms to oriented paths // Discr. Math. 1996. Vol. 132. P. 107-114.

97. C. Herrman. Affine algebras in congruence-modular varieties // Acta Sci. Math. (Szeged). 1971. Vol. 41. P. 119-125.

98. D. Hobby and R.N. McKenzie. The Structure of Finite Algebras. ProvidencerAmerican Mathematical Society. 1988. (Contemporary Mathematics. Vol. 76).

99. P.D. Hubbe and E.C. Freuder. An efficient cross product representation of the constraint satisfaction problem search space // Proc. 10th National Conference on AI. AAAI. 1992. P. 421-427.

100. H.B. Hunt III, M.V. Marathe, V. Radhakrishnan, and R.E. Stearns. The complexity of planar counting problems // SIAM J. Comput. 1998. Vol. 27. P. 1142-1167.

101. Т.Н. Jackson. Number Theory. Routledge and Kegan Paul, 1975.

102. F. Jaeger, D.L. Vertigan, and D.J.A Welsh. On the computational complexity of the Jones and Tutte polynomials // Mathematical Proc. of the Cambridge Philosophical Soc. 1990. Vol. 108. P. 35-53.

103. P.G. Jeavons. Recovering a relation from a decomposition using constraint satisfaction 11 Information Sciences. 1994. Vol. 78. P. 229-256.

104. P.G. Jeavons. On the algebraic structure of combinatorial problems // Theoretical Comput. Sci. 1998. Vol. 200. P. 185-204.

105. P.G. Jeavons and D.A. Cohen. An algebraic characterization of tractable constraints // Computing and Combinatorics. First Int. Conf. (Xi'an, 1995). Berlin:Springer-Verlag. 1995. P. 633-642. (LNCS, Vol. 959).

106. P.G. Jeavons, D.A. Cohen, and M.C. Cooper. Constraints, consistency and closure // Artificial Intelligence. 1998. Vol. 101, №1-2. P. 251-265.

107. P.G. Jeavons, D.A. Cohen, and M. Gyssens. A unifying framework for tractable constraints // Proc. 1st Int. Conf. on Constraint Programming (Cassis, 1995). Berlin:Springer-Verlag. 1995. P. 276-291. (LNCS, Vol. 976).

108. P.G. Jeavons, D.A. Cohen, and M. Gyssens. A test for tractability // Proc. 2nd Int. Conf. on Constraint Programming (Boston, 1996). Berlin:Springer-Verlag. 1996. P. 267-281. (LNCS, Vol. 1118).

109. P.G. Jeavons, D.A. Cohen, and M. Gyssens. Closure properties of constraints // J. ACM. 1997. Vol. 44. P. 527-548.

110. P.G. Jeavons, D.A. Cohen, and J.K. Pearson. Constraints and universal algebra // Annals of Math, and Artificial Intelligence. 1998. Vol. 24. P. 51-67.

111. P.G. Jeavons and M.C. Cooper. Tractable constraints on ordered domains // Artificial Intelligence. 1995. Vol. 79, №2. P. 327-339.

112. P.G. Jeavons, N.W. Dunkin, and J.E. Bater. Why higher order constraints are necessary to model frequency assignment problems // Workshop on Non-binary Constraints, 1998. P. 33-42.

113. P. Jegou. Cyclic-clustering: a compromise between tree-clustering and cycle-cutset method for improving search efficiency // Proc. ECAI'90 (Stockholm, 1990). P. 369-371.

114. P. Jegou. A new decomposition method to solve constraint-satisfaction problems // Technical report, Centre de Recherche en Informatique de Montpellier (CRIM), 1991.

115. M. Jerrum and A. Sinclair. The Markov chain Monte Carlo method: an approach to approximate counting and integration // Approximation Algorithms for NP-hard Problems. PSW. 1996. P. 482-520.

116. P. Jonsson and C. Backstrom. A unifying approach to temporal constraint reasoning // Artificial Intelligence. 1998. Vol. 102. P. 143-155.

117. K. Kearnes. Idempotent simple algebras // Lecture Notes in Pure and Appl. Math. NY:Dekker. 1996. Vol 180. pages 529-572.

118. L. Kirousis. Fast parallel constraint satisfaction // Artificial Intelligence. 1993. Vol. 64. P. 147-160.

119. P.G. Kolaitis and M.Y. Vardi. On expressive power of datalog: tools and a case study // Proc. 9th ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems. 1990. P. 61-71.

120. Ph.G. Kolaitis. Constraint satisfaction, databases, and logic // Proc. 17th Int. Joint Conf. on Artificial Intellignece. 2003. P. 31-41.

121. Ph.G. Kolaitis and M.Y. Vardi. Conjunctive-query containment and constraint satisfaction // J. Comput. Syst. Sci. 2000. Vol. 61. P. 302-332.

122. Ph.G. Kolaitis and M.Y. Vardi. A game-theoretic approach to constraint satisfaction // Proc. 17th National Conf. on Artificial Intelligence. 2000. P. 175-181.

123. G. Kondrak and P. van Beek. A theoretical evaluation of selected backtracking algorithms // Artificial Intelligence. 1997. Vol. 89. P. 365-387.

124. M. Koubarakis. From local to global consistency in temporal constraint networks // Proc. 1st Int. Conf. on Constraint Programming (Cassis, 1995). Berlin:Springer-Verlag. P. 53-69. (LNCS. 1995. Vol. 976).

125. M. Koubarakis. Tractable disjunctions of linear constraints // Proc. 2nd Int. Conf. on Constraint Programming (Boston, 1996). Berlin:Springer-Verlag. 1996. P. 297-307. (LNCS. Vol. 1118).

126. L. Krippahl and P. Barahona. Applying constraint programming to protein structure determination 11 Proc. 5th Int. Conf. on Constraint Programming. Berlin:Springer-Verlag. 1999. LNCS. Vol. 1713. P. 289-302.

127. A.A. Krokhin, P. Jeavons, and P. Jonsson. A complete classification of complexity in alien's algebra in the presence of a non-trivial basic relation // Proc. 17th Int. Joint Conf. on Artificial Intelligence (Seattle, 2001). P. 83-88.

128. V. Kumar. Algorithms for constraint satisfaction problems: A survey // AI Magazine. 1992. Vol. 13, №1. P. 32-44.

129. P.B. Ladkin and R.D. Maddux. On binary constraint problems 11 J. ACM. 1994. Vol. 41. P. 435-469.

130. R. Ladner. On the structure of polynomial time reducibility // J. ACM. 1975. Vol. 22. P. 155-171.

131. J. Lagergren. Efficient parallel algorithms for graphs // J. Algorithms. 1996. Vol. 20, №1. P. 20-44.

132. B. Larose and L. Zadori. Bounded width problems and algebras // Algebra Universalis. 2007. Vol. 56, №3-4. P. 439-466.

133. C. Lautemann. Efficient algorithms on context-free graph languages// Automata, languages and programming. Berlin:Springer-Verlag. 1988. LNCS. Vol. 317. P. 362-378.

134. J.L. Lebowitz and G. Gallavotti. Phase transitions in binary lattice gases //J. Math. Physics. 1971. Vol. 12. P. 1129-1133.

135. L.A. Levin. Universal enumeration problems // Problems on Inf. Transmission. 1973. Vol. 9. P. 265-266.

136. N. Linial. Hard enumeration problems in geometry and combinatorics // SIAM J. Algebraic and Discr. Methods 1986. Vol. 7, №2. P. 331-335.

137. L. Lovasz. The rank of connection matrices and the dimension of graph algebras // Eur. J. Comb. 2006. Vol. 26. №6. P. 962-970.

138. L. Lovasz and B. Szegedy. Limits of dense graph sequences // J. Comb. Theory, Ser. B. 2006. Vol. 96. №6. P. 933-957.

139. G.F. Luger and W.A. Stubblefield. Artificial Intelligence: Structures and Strategies for Complex Problem Solving. Redwood Cliffs:Benjamin-Cummings. 1993.

140. A.K. Mackworth and E.C. Freuder. The complexity of constraint satisfaction revisited // Artificial Intelligence. 1993. Vol. 59. P. 57-62.

141. J.P. Marques-Silva and K.A. Sakallah. Grasp — a new search algorithm for satisfiability // Proc. IEEE/ACM Int. Conf. on Computer Aided Design. 1996. P. 220-227.

142. Jin Matou§ek and Robin Thomas. On the complexity of finding iso- and other morphisms for partial k-trees // Discr. Math. 1992. Vol. 108, №1-3. P. 343-364.

143. H.A. Maurer, J.H. Sudborough, and E. Welzl. On the complexity of the general colouring problem // Information and Control. 1981. Vol. 51. P. 123-145.

144. G. McGillivray. On the complexity of colourings by vertex-transitive and arc-transitive digraphs // SI AM J. Discr. Math. 1991. Vol. 4. P. 297-308.

145. I. Meiri, R. Dechter, and J. Pearl. Uncovering trees in constraint networks // Artificial Intelligence. 1996. Vol. 86, №2. P. 245-267.

146. D. Mitchell. Resolution and constraint satisfaction // Proc. Int. Conf. on Principles and Practices of Constraint Programming. Berlin:Springer-Verlag. 2003. P. 63-79. (LNCS. Vol 2833).

147. U. Montanari. Networks of constraints: Fundamental properties and applications to picture processing // Information Sciences. Vol. 7. P. 95-132.

148. B.A. Nadel. Constraint satisfaction in Prolog: Complexity and theory-based heuristics // Information Sciences. 1995. Vol. 83, №3-4. P. 113-131.

149. B.A. Nadel and J. Lin. Automobile transmission design as a constraint satisfaction problem: Modeling the kinematik level // Artificial Intelligence for Engineering Design, Anaysis and Manufacturing. 1991. Vol. 5, №3. P. 137-171.

150. B. Nebel and H.-J. Biirckert. Reasoning about temporal relations: a maximal tractable subclass of Allen's interval algebra // J. ACM. 1995. Vol. 42. P. 43-66.

151. J. NeSetril and X. Zhu. On bounded treewidth duality of graphs // J. Graph Theory. 1996. Vol. 23. P. 151-162.

152. J. NeSetril and X. Zhu. On sparse graphs with given colorings and homomorphisms // J. Comb. Theor B. 2004. Vol. 90. P. 161-172.

153. C.H. Papadimitriou. Computational Complexity. NY:Addison-Wesley, 1994.

154. I. Pe'er and R. Shamir. Satisfiabilty problems on intervals and unit intervals // Theor. Comput. Sci. 1997. Vol. 175. P. 349-372.

155. R. Poschel and L.A. Kaluznin. Funktionen- und Relationenalgebren. Berlin:DVW. 1979.

156. E.L. Post. The two-valued iterative systems of mathematical logic. Princeton University Press. 1941. (Annals Mathematical Studies. Vol. 5).

157. J.S. Provan and M.O. Ball. The complexity of counting cuts and of computing the probability that a graph is connected // SIAM J. Comput. 1983. Vol. 12, №4. P. 777-788.

158. C.R. Reeves. Modern Heuristic Techniques for Combinatorial Problems. NY:John Wiley & Sons. 1995.196. 0. Reingold. Undirected st-connectivity in log-space // Technical Report TR04-094, ECCC, 2004.

159. J. Renz. Mammal tractable fragments of the Region Connection Calculus: a complete analisis // Proc. 17th Int. Conf. on Artificial Intelligence (Stockholm, 1999). P. 541-550.

160. J. Renz and B. Nebel. On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus // Artificial Intelligence. 1999. Vol. 108. P. 69123.

161. N. Robertson and P.D. Seymour. Graph width and well-quasi-ordering // Progress in graph theory. Toronto-.Academic Press. 1984. P. 399-406.

162. A. Romanowska. Mal'cev modes, affine spaces and barycentric algebras // Universal algebra and quasigroup theory (Jadwisin, 1989). Berlin:Heldermann. 1992. P. 173-194. (Res. Exp. Math. Vol. 19).

163. I.G. Rosenberg. Minimal clones I: the five types // Lectures in Universal Algebra (Proc. Conf. Szeged 1983). Amsterdam: North-Holland. 1986. P. 405-427 (Colloq. Math. Soc. Jânos Bolyai. Vol. 43).

164. Ivo G. Rosenberg. Mal'cev algebras for universal algebra terms // Algebraic logic and universal algebra in computer science (Ames, IA, 1988). BerlimSpringer. 1990. P. 195-208. (LNCS. Vol. 425).

165. T.J. Schaefer. The complexity of satisfiability problems // Proc. 10th ACM Symp. on Theory of Computing. 1978. P. 216-226.

166. P. Scheffler. Linear-time algorithms for NP-complete problems restricted to partial k-trees. Akademie der Wissenschaften der DDR Karl-Weierstrass-Institute fur Mathematik. Berlin. 1987. (Report MATH. Vol. 87).

167. E. Schwalb and L. Vila. Temporal constraints: a survey // Constraints. 1998. Vol. 3, №2-3. P. 129-149.

168. Y. Shahar. Timing is everything: temporal reasoning and temporal data maintanence in medicine // Artificial Intelligence in Medicine. 1999. (Lecture Notes in Artificial Intelligence. Vol. 1620).

169. Jonathan D. H. Smith. Mal'cev varieties. Berlin:Springer-Verlag. 1976. (Lecture Notes in Mathematics. Vol. 554).

170. B. Szczepara. Minimal clones generated by groupoids. PhD thesis, Université de Montreal, 1996.

171. A. Szendrei. Clones in Universal Algebra. Université de Montreal. 1986. (Séminaires de Mathématiques Supérieures. Vol. 99).

172. A. Szendrei. Simple surjective algebras having no proper subalgebras // J. Australian Math. Soc. (Ser. A). 1990. Vol. 48. P. 434-454.

173. S. Toda and M. Ogiwara. Counting classes are at least as hard as the polynomial-time hierarchy // SI AM J. Coraput. 1992. Vol. 21, №2. P. 316-328.

174. E. Tsang. Foundations of Constraint Satisfaction. London:Academic Press. 1993.

175. S.P. Vadhan. The complexity of counting in sparse, regular and planar graphs // SIAM J. Comput. 2001. Vol. 31, №2. P. 398^127.

176. L. Valiant. The complexity of computing the permanent // Theor. Comput. Sci. 1979. Vol. 8. P. 189-201.

177. L. Valiant. The complexity of enumeration and reliability problems // SIAM J. Comput. 1979. Vol. 8, №3. P. 410-421.

178. P. van Beek. On the minimality and decomposability of row-convex constraint networks // Proc. AAAI-92 (San Jose, 1992), P. 447-452.

179. P. van Beek. Reasoning about qualitative temporal information // Artificial Intelligence. 1992. Vol. 58. P. 297-326.

180. P. van Hentenryck, Y. Deville, and C-M. Teng. A generic arc-consistency algorithm and its specializations // Artificial Intelligence. 1992. Vol. 57. P. 291-321.

181. M.Y. Vardi. On the complexity of bounded-variables queries // Proc. 14th ACM Symp. on Priciples of Database Systems. ACM Press. 1995. P. 266-276.

182. M.Y. Vardi. Constraint satisfaction and database theory: a tutorial // Proc. 19th ACM Symp. on Priciples of Database Systems. ACM Press. 2000. P. 173-182.

183. L. Vila. A survey on temporal reasoning in artificial intelligence // AI Communications. 1994. Vol. 7, №1. P. 4-28.

184. M. Vilain, H. Kautz, and P. van Beek. Constraint propagation algorithms for temporal reasoning: A revised report // Readings in Qualitative Reasoning about Physical Systems (D.S. Weld and J. de Kleer, eds.). NY:Morgan Kaufmann. 1989. P. 373-281.

185. M. Wiegers. The k-section of treewidth restricted graphs // Mathematical foundations of computer science (Banska Bystrica, 1990). BerlinrSpringer-Verlag. 1990. P. 530-537. (LNCS. Vol 452).

186. T. V. Wimer. Linear algorithms for the dominating cycle problems in series-parallel graphs, partial k-trees, and Halin graphs // Congressus Numerantium. 1987. Vol. 57. P. 289-298.

187. T. V. Wimer, S. T. Hedetniemi, and R. Laskar. A methodology for constructing linear graph algorithms j/ Proc. Sundance Conf. on Combinatorics and related topics. 1985. Vol. 50. P. 43H50.

188. H. Zhang. Sato: an efficient propositional prover // Proc. Int. Conf. on Automated Deduction. 1997. P. 272-275. (LNAI. Vol. 1249).

189. L. Zhang, C.F. Madigan, M.W. Moskewicz, and S. Malik. Efficient conflict driven learning in a Boolean satisfiability solver // Proc. Int. Conf! on Computer Aided Design. 2001. P. 279-285.Работы автора по теме диссертации

190. A.A. Bulatov, P.G. Jeavons, and A.A. Krokhin. Constraint satisfaction problems and finite algebras // Proc. 27th Int. Colloq. on Automata, Languages and Programming. Berlin:Springer-Verlag. 2000. P. 272-282. (LNCS. Vol. 1853).

191. A.A. Bulatov, P.G. Jeavons, and A.A. Krokhin. The complexity of maximal constraint languages // Proc. 33rd Ann. ACM Symp. on Theory of Computing (Hersonissos, 2001). ACM Press. 2001. P. 667-674.

192. A. Bulatov and P. Jeavons. Algebraic structures in combinatorial problems // Technical Report. Technische Universität Dresden. 2001. MATH-AL-4-2001.

193. A. Bulatov and P. Jeavons. Algebraic approach to multi-sorted constraints // Technical Report. University of Oxford. 2001. PRG-RR-01-18.

194. A.A. Bulatov. A dichotomy theorem for constraints on a three-element set // Proc. 43rd IEEE Symp. on Foundations of Computer Science (Vancouver, 2002). IEEE Computer Society. 2002. P. 649-658.

195. A.A. Bulatov and P.G. Jeavons. An algebraic approach to multi-sorted constraits // Proc. 9th Int. Conf. on Principles and Practice of Constraint Programming (Kinsale,2003). P. 197-202.

196. A.A. Bulatov, P.G. Jeavons, and A.A. Krokhin. Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey // Proc. 33rd IEEE International Symp. on Multiple-Valued Logic (Tokyo, 2003). P. 343-351.

197. A.A. Bulatov. Tractable conservative constraint satisfaction problems // Proc. 18th Annual IEEE Symp. on Logic in Computer Science (Ottawa, 2003). IEEE Computer Society. 2003. P. 321-330.

198. A. Bulatov and V. Dalmau. Towards a dichotomy theorem for the counting constraint satisfaction problem // Proc. 44th IEEE Symp. on Foundations of Computer Science (Cambridge, 2003). IEEE Computer Society. 2003. P. 562-571.

199. A. Bulatov and M. Grohe. The complexity of partition functions // Proc. 31st Int. Colloq. on Automata, Languages and Programming (Turku, 2004). P. 294-306.

200. A.A. Булатов. Сложность консервативной задачи Обобщенная Выполнимость // ДАН РАН. 2004. Т. 397, №5. С. 583-585.

201. A. Bulatov. A graph of a relational structure and constraint satisfaction problems // Proc. 19th IEEE Ann. Symp. on Logic in Computer Science (Turku,2004). P. 448-457.

202. A.A. Булатов. Сложность задач о подсчете числа решений // Изв. Уральского госуниверситета. Математика и механика. 2005. Т. 36. С. 67-82.

203. A.A. Bulatov, P.G. Jeavons, and A.A. Krokhin. Classifying complexity of constraints using finite algebras // SIAM J. Comput. 2005. Vol. 34, №3. P. 720-752.

204. Andrei A. Bulatov and Martin Grohe. The complexity of partition functions // Theor. Comput. Sci. 2005. Vol. 348, №2-3. P. 148-186.

205. Andrei A. Bulatov. H-coloring dichotomy revisited // Theor. Comput. Sci. 2005. Vol. 349, №1. P. 31-39.

206. А.А. Булатов. Полиномиальностъ мальцевских задач CSP // Алгебра и логика. 2006. Т. 45, №6. С. 655-686.

207. A. Bulatov. Three-element Mal'tsev algebras // Acta Sci. Math (Szeged). 2006. Vol. 298, №2. P. 321-344.

208. A.A. Bulatov. Combinatorial problems raised from 2-semilattices // J. Algebra. 2006. Vol. 298, №2. P. 321-339.

209. Andrei A. Bulatov. A dichotomy theorem for constraint satisfaction problems on a 3-element set U J. ACM. 2006. Vol. 53, №1. P. 66-120.

210. Andrei A. Bulatov and Victor Dalmau. A simple algorithm for mal'tsev constraints // SIAM J. Comput. 2006. Vol. 36, №1. P. 16-27.

211. Andrei A. Bulatov and Victor Dalmau. Towards a dichotomy theorem for the counting constraint satisfaction problem // Inf. Comput. 2007. Vol. 205, №5. P. 651-678.

212. A.A. Bulatov, P.G. Jeavons, and M.V. Volkov. Finite semigroups imposing tractable constraints // Semigroups, Algorithms, Automata and Languages (Gracinda M.S.Gomes, Jean-Eric Pin, Pedro V.Silva, eds.). Singapore:World Scientific. P. 313-329.

213. A. Bulatov and V. Skvortsov. Amalgams of constraint satisfaction problems // Proc. 18th Int. Joint Conf. on Artificial Intelligence (Acapulco, 2003). P. 197-202.

214. A. Bulatov, F. Borner, A. Krokhin and P. Jeavons. Quantified constraints: algorithms and complexity // Proc. 17th Int. Workshop on Computer Science Logic (Vienna, 2003). Berlin:Springer-Verlag. 2003. P. 58-70. (LNCS, Vol. 2803).

215. A. Bulatov, H, Chen and V. Dalmau. Lcarnability of relatively quantified generalized formulas II Proc. 15th Int. Conf. on Algorithmic Learning Theory (Padova, 2004). IEEE Computer Society. 2004. P. 365-379.

216. A. Atserias, A. Bulatov and A. Dawar. Affine systems of equations and counting infinitary logic ¡I Proc. 35th Int. Colloq. on Automata, Languages and Programming. Berlin:Springer-Verlag. 2007. P. 558-570. (LNCS. Vol. 4596).