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

, 1 У —'

РОССИЙСКАЯ АКАДЕМИЯ НАУК УРАЛЬСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ

□ОЗ16Э1У4

На правах рукописи

Булатов Андрей Арнольдович

АЛГЕБРАИЧЕСКИЕ МЕТОДЫ В ИССЛЕДОВАНИИ КОМБИНАТОРНЫХ ЗАДАЧ

01.01.06 — математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ диссертации на соискание ученой степепи доктора физико-математических наук

1 5 МАЙ 2003

003169134

РОССИЙСКАЯ АКАДЕМИЯ НАУК УРАЛЬСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ

На правах рукописи

Булатов Андрей Арнольдович

АЛГЕБРАИЧЕСКИЕ МЕТОДЫ В ИССЛЕДОВАНИИ КОМБИНАТОРНЫХ ЗАДАЧ

01.01.06 — математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

Работа выполнена на кафедре алгебры и дискретной математики Уральского государственного университета им А М Горького

Научный консультант: заслуженный деятель науки

Российской Федерации, академик Европейской академии наук профессор Л. Н ШЕВРИН

Официальные оппоненты: доктор физ -мат наук

профессор А Г ПИНУС доктор физ -мат. наук профессор Д А БРЕДИХИН доктор физ -мат наук профессор О Г ХАРЛАМПОВИЧ

Ведущая организация: Институт математики

им С Л Соболева СО РАН

Защита диссертации состоится 20 мая 2008 г в 14 часов на заседании диссертационного совета Д 004 006 03 в Институте математики и механткт УрО РАН по адресу

620219, г Екатеринбург, ул Софьи Ковалевской, 16

С диссертацией можно ознакомиться в библиотеке Института математики и механики УрО РАН.

Автореферат разослан 20 апреля 2008 г

-Ученый секретарь__

диссертационного совета „ „ „ ,

Д 004 006 03 В В Кабанов

д ф -м н , с н с

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В комбинаторной задаче CSP1 требуется выяснить, выполнима ли в данной модели диофантова формула, те экзистенциальная формула первой ступени, бескванторная часть которой является конъюнкцией атомарных формул2 Эта задача в течение долгого времени служит объектом исследований в трех областях математики и информатики искусственном интеллекте, логике и теории баз данных, а также теории графов и некоторых разделах комбинаторики. Важной разновидностью задачи CSP является задача о подсчете числа решений, #CSP, условие которой совпадает с условием задачи CSP и требуется найти число выполняющих присваиваний свободным переменным заданной формулы

В искусственном интеллекте и приложениях теоретической информатики задача CSP рассматривается в качестве средства для систематизации и унификации широкого спектра имеющихся комбинаторных алгоритмов, а также разработки универсальных алгоритмов, не зависящих от частных особенностей той или иной задачи Представление на языке CSP часто позволяет избежать разработки специфического алгоритма для конкретной комбинаторной задачи Вместо этого достаточно записать ее в форме CSP, а затем воспользоваться одним из известных алгоритмов В последние годы возникают универсальные решатели комбинаторных задач, входом для которых служит описание комбинаторной задачи в терминах CSP Развитие универсальных решателей этого типа и языков представления задач в CSP-форме признано ACM (Association for Computing Machinery) одним из стратегических направлений в развитии теоретической информатики

Общая задача CSP была сформулирована в 1974 году Монтанари [95], который использовал ее для моделирования пространственных взаимосвязей между объектами. С тех пор появились сотни статей и несколько монографий, посвященных различным аспектам задачи CSP, см , например, [16,18, 26, 42, 45,48, 70, 71, 82,83,89, 90, 91,105, 108] Задача CSP применяется во многих областях информатики, включая временную и пространственную логику [105], распознавание зрительных образов [95], автоматическое доказательство теорем

*От английского "Constraint Satisfaction Problem", в немногочисленных русскоязычных работах по этой проблематике встречается также название "Обобщенная выполнимость"

2Такие формулы называются также примитивно позитивными

[25], техническое проектирование [97], анализ языков программирования [96] и естественных языков [2], биоинформатику [81]

Первой точкой пересечения логики и задачи CSP является задача Выполнимость и ее обобщение — задача Обобщенная выполнимость, в которой вместо элементарных дизъюнкций допускаются произвольные булевы предикаты В решении этих задач широко используются логические методы, такие как теория доказательств, разнообразные версии метода резолюций и другие [1, 94] Следующей важной вехой в исследовании логических аспектов задачи CSP явилась статья Федера и Варди [42]. В этой работе они дали эквивалентное определение задачи CSP как задачи о существовании гомоморфизма между двумя конечными моделями Такое теоретико-модельное определение позволяет описывать классы частных задач CSP в терминах различных логик, а также связать задачу CSP с результатами о сохранении в теории конечных моделей Ярким примером работ в данном направлении является результат Атсериса и Россмана [3, 103], доказавших, что если класс конечных моделей, представимый как класс всех гомоморфных прообразов некоторой конечной модели, может быть охарактеризован формулой первого порядка, то он может быть охарактеризован отрицанием позитивной экзистенциальной формулы3

В теории баз данных диофантовы формулы из задачи CSP соответствуют так называемым конъюнктивным запросам к базам данных Естественными задачами относительно таких запросов являются задача построения ответа на запрос и задача сравнения двух запросов Чандра и Мерлин [10] показали, что эти задачи эквивалентны, а Варди и Колаитис [80] доказали, что они эквивалентны задаче CSP Данные работы открыли путь для интенсивного взаимодействия между двумя областями, см , напр , [15, 27, 44, 47, 48, 49, 50, 51, 54, 73, 74] Ведущей темой этих работ является описание структуры запросов к базе данных (соответственно структуры примитивно позитивных формул из задачи CSP), которая обеспечивала бы возможность эффективной их обработки Еще одним направлением, возникшим в последние годы, является использование задач CSP для эффективного преобразования баз данных и предачи дан-

3В своей работе [103] Россман доказал значительно более сильный результат, а именно, формулапервогопорядка^обладающая следующим свойством еслиона верна на некоторой конечной модели, то она также верна на любом гомоморфном образе этой модели, эквивалентна некоторой позитивной экзистенциальной формуле

пых между ними [36, 46, 78, 79] Задачи о подсчете числа решений также имеют важные приложения в разделе теории баз данных, занимающимся изучением "реальных" баз данных [64]

Многие задачи теории графов, в особенности связанные с гомоморфизмами, раскрасками и упаковками графов, естественным образом представляются в виде частных случаев задачи CSP (см , например, [56, 57]), и зачастую допускают использование методов теории CSP Наиболее заметными работами в данном направлении являются [4,5, 6, 37, 38, 39, 40, 41, 53, 58, 59, 60, 92, 93, 98, 99] Задачи о нахождении числа решений также активно изучались в данном контексте [29, 30, 31, 33, 35] Кроме того, задачи данного типа тесно связаны с так называемыми функциями разбиении, введенных в статистической физике [85], а также графовыми параметрами [43, 87, 88] К настоящему времени сложилось три основных направления в изучении задачи CSP создание универсальных алгоритмов, решающих большинство задач CSP за приемлемое время, выявление подзадач задачи CSP, которые могут быть решены эффективно, исследование комбинаторных задач из различных областей математики в контексте задачи CSP Вопросы, рассматриваемые в данной диссертации, относятся в основном ко второму из перечисленных направлений

Задача CSP является NP-полной [95], следовательно, в предположении P^NP, универсального полиномиального алгоритма для нее не существует Однако многие ее подзадачи имеют меньшую вычислительную сложность Таким образом, изучение ограниченных подзадач этой задачи является естественным и важным для приложений направлением исследований

Одним из основных путей задания ограничений на задачу CSP является следующий (Мы используем теоретико-модельное определение CSP как вопроса о существовании гомоморфизма из заданной конечной модели Q в заданную конечную модель 7Z ) Для класса Г конечных моделей через СБР(Г) обозначается множество всех частных задач CSP, в которых модель 7L принадлежит Г Если Г одноэлементен, скажем, Г — {71}, мы используем обозначение CSP(7?.) Задачи #CSP о подсчете числа решений может быть ограничена аналогичным образом Такие задачи мы обозначаем через #CSP(r)

Изучение ограниченных задач CSP началось с пионерской работы Шефера [104], в которой он показал, что существует 6 множеств 2-элементных моделей, для которых эта задача может быть решена за полиномиальное время, если же класс 2-элементных мо-

делей не принадлежит ни одному из указанных множеств, то задача КР-полна Этот результат получил название теорема Шефе-ра о дихотомии Позднее были предприняты попытки обобщить результат Шефера на множества произвольных конечных моделей В частности, в [28, 66, 112] была показана полиномиальная разрешимость нескольких типов задач, обобщающих 2-Вып0ЛНИМ0СТЬ, в [11, 68, 72, 76, 142] изучались обобщения задачи Хорновская выполнимость, статья [7] содержит некоторые результаты о моделях, отношения в которых выразимы с помощью операций полуколец, в [14, 13, 143] изучались классы моделей, которые могут быть представлены в виде объединения меньших моделей Примечательно, что во всех известных случаях ограниченная задача СЭР либо может быть решена за полиномиальное время, либо КР-полна Это позволило Федеру и Варди [42] сформулировать гипотезу о дихотомии, утверждающую, что каждая задача вида С8Р(72.) либо решается за полиномиальное время, либо КР-полна Гипотеза о дихотомии остается открытой, что позволяет сформулировать следующую

Проблема 1Б (Проблема дихотомии) Выяснить, верно ли, что для любого класса Г конечных моделей задача СЭР(Г) либо полиномиальна, либо ИР-полна

Значительный интерес представляет также уточнение данной проблемы

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

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

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

Отметим, что для случая, когда Г — множество 2-элементных моделей, результаты работы [104] полностью решают проблемы 1С,113 Проблема 1М в этом случае полностью решена в [80].

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

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

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

Ограниченные задачи о подсчете числа решений, #С8Р, также привлекали значительное внимание исследователей Для задач такого типа аналогами классов Р и № служат классы РР, класс задач о вычислении функции, решаемых за полиномиальное время, и класс #Р, класс задач о подсчете, полученных из задач класса № В частности, в [17] были охарактеризованы классы Г 2-элементных моделей, для которых задача Ц СЭР (Г) разрешима за полиномиальное время, в [52] охарактеризованы графы для которых решается за полиномиальное время Существует также внушигель-ный массив работ, в которых рассматриваются задачи о нахождении числа гомоморфизмов в ориентированные графы различных видов, задачи нахождения числа гомоморфизмов с дополнительными ограничениями, а также гомоморфизмов графов с дополнительными ограничениями, см , например, [8, 17, 18, 30, 31, 32, 35, 34, 33, 52, 62, 75, 86, 100, 109, 111, 110] Отметим, что результат статьи [17] аналогичен теореме Шефера о дихотомии, так как он показывает, что каждая задача вида //ОБР (Г) либо полиномиальна, либо #Р-полна Как и в случае задачи распознавания СБР, во всех известных случаях ограниченные задачи о подсчете числа решений либо разрешимы за полиномиальное время, либо #Р-полны Таким образом, актуальными являются следующие проблемы, аналогичные проблемам, отмеченным выше

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

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

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

Новый импульс исследованиям ограниченных задач СЭР был придал открытием Джевонсом и его соавторами в [65, 70] алгебраического подхода к изучению СЭР. Этот подход основан на использовании алгебраических свойств моделей из Г Джевонс доказал, что для любых конечных моделей 71\ и 7^2 если каждый полиморфизм 71\ является также полиморфизмом 72-2, то СБР^г) сводится за полиномиальное время к СЭР^х) Таким образом, сложность ограниченных задач СБР зависит исключительно от множества полиморфизмов соответствующих моделей

Используя полиморфизмы, Джевонсу и другим удалось объяснить разрешимость за полиномиальное время многих известных классов СБР, а также значительно обобщить предшествующие результаты в этой области В частности, показано, что задача СЭР (72) может быть решена за полиномиальное время, если одна из следующих операций является полиморфизмом Л константная, полурешеточная, функция почти единогласия, аффинная операция х — у + г конечной абелевой группы Результат о константных операциях расширяет класс непозитивных и ненегативных конъюнктивных нормальных форм из теоремы Шефера, задачи СБР, соответствующие моделям с полурешеточным полиморфизмом, включают в себя задачи с хорновскими и анти-хорновскими КНФ, арифметическими ограничениями [113] и ограничениями, замкнутыми относительно взятия максимума [72], задачи, соответствующие моделям, полиморфизмом которых является функция почти единогласия, обобщают задачу 2-Выполнимость, задачу СЭР с импликационными ограничениями, а также класс СЭР, названный 0/1/Аьь [68, 76], наконец, задачи, соответствующие моделям с аффинным полиморфизмом позволяют решать системы линейных уравнений [68] Позже Далмау [20] показал, что присутствие операций парапримальной алгебры в качестве полиморфизмов также влечет полиномиальную разрешимость соответствующей задачи СЭР

С другой стороны, ^-полные задачи СЭР также получили объяснение на языке полиморфизмов если модель 72 имеет лишь неконстантные унарные полиморфизмы, то задача СЭР (71) КР-нолна Это имеет место, например, в случае полных графов и, следовательно, применительно к задаче й-Раскраска графа

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

Полиморфизмы были использованы в [21] при попытке охарактеризовать задачи CSP, решаемые с недетерминированной логарифмической памятью В [67] показано, что если модель 7Z имеет полиморфизм, являющийся fc-местной функцией единогласия, то GSP(72.) может быть решена программой на язаке Даталог, имеющей не более к переменных в каждом правиле Наконец, в [12, 24] были введены понятия более общие, чем полиморфизмы В первой из этих статей с помощью полиморфизмов удалось охарактеризовать задачи CSP, решаемые Даталог-программами определенного типа, а во второй — задачи CSP, решаемые с помощью некоторого специального алгоритма

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

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

универсально-алгебраические методы, а именно, методы теории решеток, теории коммутаторов и теории ручных конгруэнций Второй тип составляют методы теории сложности, те сводимости различных видов, таких, как полиномиальная сводимость по Карпу, сводимость по Тьюрингу, сводимость с логарифмической памятью Наконец, методы третьего типа включают в себя использование алгебраических понятий и фактов для построения комбинаторных алгоритмов для решения задач CSP распознавания и задач о подсчете числа решений

Научная новизна. Все результаты диссертации являются новыми

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

Апробация работы. Результаты диссертации были представлены на международных симпозиумах по автоматам, языкам и программированию (Женева, 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-2007), на семинаре "Алгебра и логика" в Новосибирске (2005,2006), и на семинаре "Алгебраические системы" в Екатеринбурге (2000-2006)

Публикации. По теме диссертации опубликовано 27 работ [115]-[141], из которых 8 статей [125, 127, 132, 135, 141, 140, 139, 138] в журналах из списка ВАК Из 27 публикаций 13 работ [115, 116, 117, 118, 120, 121, 123, 124, 128, 129, 130, 136, 137] являются совместными В статьях [117, 118, 120, 128], а также тезисах конференций [115, 120], автору принадлежит подавляющая часть доказательств В работе [137] и соответствующих тезисах конференций [123] автору принадлежат доказательства всех результатов, исключая сведение к случаю идемпотентных алгебр Статьи [121, 129] являются обзорами, в стагье [116] автору принадлежит результат о полиномиаль-ности алгебр с минимальным клоном термальных операций, порожденным операцией консервативного коммутативного группоида Заметим, что результаты этой статьи были значительно обобщены в [126] В статье [136] приводится упрощенная, хотя и менее мощная, версия алгоритма из [132], эта статья написана в нераздельном соавторстве с В Далмау Статья [130] (и соответствующие тезисы на конференциях [124]) написана в нераздельном соавторстве с М Гроэ

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

Объем и структура работы. Диссертационная работа состоит из введения, трех глав, списка литературы (260 наименований) и тематического указателя Работа занимает 322 страниц текста

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

СОДЕРЖАНИЕ РАБОТЫ

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

Обозначим через Pol (Л) множество всех полиморфизмов конечной модели Л с носителем А, а через Alg(«4) — алгебру (Л, Pol (Л)) Для конечной алгебры А = (А; F) через Inv(A) мы обозначаем множество всех отношений инвариантных относительно операций из F, а через Str(A) — множество всех моделей А с носителем А, для которых Pol (Л) 2 F Алгебра А называется полиномиальной, если задача CSP(«4) может быть решена за полиномиальное время для любой модели А G Str(A), алгебра называется NP-полной, если задача СБР(Л) NP-полна для некоторой модели А € Str(A)

Теорема 1. (1) Пусть А — конечная модель Задача CSP(^) полиномиальна тогда и только тогда, когда алгебра AIg(.A) полиномиальна, СЭР(Л) NP-полна тогда и только тогда, когда Alg(„4) NP-полна

(2) Пусть А — конечная алгебра Если А полиномиальна, то любая конечная алгебра из многообразия порожденного А также полиномиальна Если некоторая алгебра из этого многообразия NP-полна, то А также NP-полна

Таким образом, сложность ограниченных задач CSP полностью определяется свойствами соответствующих многообразий Следующий результат показывает, что достаточно изучать лишь идемпо-тентные многообразия Пусть А = (А, F) — конечная алгебра, е — унарный идемпотентный терм (те. удовлетворяющий равенству е(е(х)) = е(ж)) и U = е{А) Тогда алгебра В = (t/; Fe), где Fe = {/^ |

/ термальная операция А и /([/, ,U) QU), называется термальпо индуцированной для А Обозначим через ld(A) полный идемпотентный редукт алгебры А

Теорема 2. (1) Пусть А — конечная алгебра и В — алгебра, термальпо индуцированная для А Алгебра А полиномиальна [NP-полна] тогда и только тогда, когда алгебра В полиномиальна [ТУР-полна] __(2)_Пустъ А — конечная сюръективнал алгебра Алгебра А полиномиальна [NP-полна] тогда и только тогда, когда алгебра \А(к) полиномиальна [NP-полна]

Теория ручных конгруэнций [61] позволяет связать многие свойства многообразий с набором типов простых интервалов в решетках конгруэнций конечных алгебр, содержащихся в многообразии. Эти типы отражают локальное строение алгебры Имеются следующие 5 типов интервалов, в соответствии с ними локально алгебра имеет структуру 1 конечного С-множества, те множества с действующей на нем группой, 2 конечного векторного пространства, 3 двухэлементной булевой алгебры, 4 двухэлементной решетки, 5 двухэлементной полурешетки Алгебра избегает тип 1, если ее решетка конгруэнций не содержит простых интервалов, помеченных типом 1 Многообразие избегает тип 1, если каждая конечная алгебра из этого многообразия избегает данный тип

Теорема 3. (1) Если многообразие, порожденное конечной алгеброй А, содержит конечную алгебру, все операции которой тривиальны, то А ИР-полна

(2) Каждая конечная идемпотентная полиномиальная алгебра избегает тип 1 Если конечная идемпотентная алгебра не избегает тип 1, то она ЫР-полна

Алгебры всех известных ^-полных ограниченных задач СЗР, см , например, [65, 68,69, 70, 71], удовлетворяют условиям теоремы 3 Более того, во всех известных случаях если алгебра не удовлетворяет этим условиям, то она является полиномиальной [9, 20, 22, 23, 63, 68, 72, 77] Естественным, таким образом, является следующее предположение, уточняющее проблемы дихотомии 1Б и классификации 1С

Гипотеза 1 (Гипотеза о дихотомии) Идемпотентная алгебра является полиномиальной тогда и только тогда, когда многообразие ею порожденное избегает тип 1

Результаты диссертации, подтверждающие это предположение в ряде случаев, приведены ниже

Если гипотеза 1 верна, то проблема распознавания 2М имеет следующее решение Рассматриваются три комбинаторные задачи Полиномиальная алгебра дана конечная идемпотентная алгебра, определить, избегает ли многообразие ею порожденное тип 1 Полиномиальная /с-модель дана модель А, содержащая не более к элементов, и такая, что все ее полиморфизмы идемпотентны, определить, избегает ли многообразие, порожденное алгеброй А^(.А), тип 1 Задача Полиномиальная модель формулируется как задача Полиномиальная /с-модель, в которой ограничение на число элементов ослаблено до требования конечности задаваемой модели

Теорема 4. Задачи Полиномиальная алгебра и Полиномиальная /с-модель полиномиальны, задача Полиномиальная модель NP-трудна

Полиномиальные алгебры. Бинарная операция называется 2-полурешеточной, если она идемпотентна, коммутативна и удовлетворяет тождеству х ■ (х у) = х у

Теорема 5. Если многообразие имеет 2-полурешеточный термальную операцию, то каждая его конечная алгебра полиномиальна

Этот результат обобщает аналогичный результат [71] (см. также [65, 70, 72]), для полурешеточной операции

В [42] изучались задачи вида CSP(.A), где А — модель, имеющая в качестве полиморфизма операцию xy-1z некоторой конечной группы В частности, было показано, что задачи данного вида могут быть решены за полиномиальное время Отметим, что указанная операция является мальцевской, т е удовлетворяет тождествам fix,у,у) = f (у, У, х) = х

Теорема 6. Если многообразие имеет мальцевский термальную операцию, то каждая его конечная алгебра полиномиальна

Данный результат обобщает результат [20], утверждающий, что любая парапримальная алгебра (каждая такая алгебра имеет маль-цевскую термальную операцию) полиномиальна

Результаты о дихотомии: строго простые алгебры. Алгебра называется строго простой, если она проста и не имеет собственных подалгебр, кроме, быть может, одноэлементных Строго простые алгебры были исчерпывающим образом описаны в [107]

Пусть G — группа перестановок, действующая на множестве А Через R(G) мы обозначаем множество операций на А, сохраняющее отношения вида {(a, g(a)) | а € А}, где д б G, а через F((7) — множество идемпотентных операций из R(G). Пусть к А = (Л, +, К) — конечномерное векторное пространство над конечным полем К, Т{А) — группа трансляций {х + а | а А} и End к А — кольцо эндоморфизмов пространства кА.-Тогда А может рассматриваться как модуль над End к А Этот модуль обозначается через jEnd кд)А Наконец, пусть обозначает множество всех операций, сохраняющих

отношение

= ((°ь I € Ак | аг — 0 по крайней мере для одного индекса г, 1 < г < к],

где 0 — некоторый фиксированный элемент из А Пусть также = Любая идемпотентная строго простая алгебра с носителем А термально эквивалентна одной из следующих алгебр.

(а0) (Л,Р((7)), где б — группа перестановок, действующая на А и такая, что каждая нетождественная перестановка из в имеет не более одной неподвижной точки;

(Ь°) (Л, М((Епс) ка)А))> гДе к А — конечномерное векторное пространство над конечным полем К,

(с!) (Л, Р(С) ПР°) для некоторого к (2 < к < со), некоторого элемента 0 € А и некоторой группы перестановок б, действующей на Л, таких, что 0 — единственная неподвижная точка каждой нетождественной перестановки из £7,

(е) (Л, Р), где |А\ = 2 и Р содержит полурешеточную операцию, 2-элементная алгебра с пустым множеством основных операции

Теорема 7. Идемпотентная строго простая алгебра полиномиальна тогда и только тогда, когда она имеет вид (а0), (Ь°), (<!) или (е) Если алгебра имеет вид (Г), то она ЫР-полпа

Следствие 1. Идемпотентная строго простая алгебра полиномиальна тогда и только тогда, когда она порождает многообразие, избегающее тип 1. В противном случае она МР-полпа

Результаты о дихотомии: 3-элементные алгебры. Пусть А — 3-элементная идемпотентная алгебра, Я £ \т(Р) — (п-местное) отношение и IV = {гь ,1к} £ {1, , п} Через рги, обозначается к-местное отношение {(а^], ,а[г^]) | а 6 /?.} Для 2-элементной подалгебры В алгебры А через II обозначается множество {г € п | рггД = А}, а через IV — множество {г е п | В С рггД} Через вц(Я) обозначается отношение эквивалентности на IV, определяемое следующим образом

{(г,.?) | Для любого а £ Я, либо а[г],а[^] £ В, либо а[г],а[?] ^ В}

Пусть также , —- это классы данного отношения эквива-

лентности Напомним, что графиком отображения / А —> В называется бинарное отношение {(а, /(а)) | а £ А} Отношение Я называется неприводимым, если для любых индексов г, ,7 множество рг|г ^Я не является графиком никакого взаимно-однозначного отображения Алгебра А

• удовлетворяет частичному 0-свойству, если существует множество 2 ее подалгебр и элемент г® € В для каждого В £ 2 такие, что А £ 2 и для любого отношения Я £ и лю-

бого кортежа а € Я найдется кортеж Ь С Я, определенный следующим образом

ЬЭД _ | ^В) если = В е Я,

а[г] в противном случае, удовлетворяет разрезающему свойству, если каждое (п-местное) отношение Я в может быть представлено в виде ргиЯ х

рг^Я, и ргуЛ = АМ,

удовлетворяет (а — 6)-заместительному свойству, а € А — В и Ь £ В, если дня любого (п-местного) В, 6 1т/(.Р) и любого кортежа аеЛ найдется кортеж Ь £ Я такой, что Ь, если а[г] = аи рггЯ = А,

1 а[г] в противном случае,

называется Ш-прямоугольпой, если для каждого отношения Я £ выполнено

рг^Д ПВ^ = (рг^ЯпВ^1) х . х (рг^ЯЛВ^),

и для любого аёД такого, что а[г] £ В для всех г £ IV. существует Ь € Я, определенный следующим образом

Ъ[г] =

а[г], если г £ Ш или |рг,Д| = 1, с в противном случае, где {с} = В П рггЯ,

• называется В-полупрямоуголъной, если отношение эквивалентности 7], классы которого равны В и А — В = {с}, является конгруэнцией алгебры А и для любого (п-местного) отношения Я £ \пм(Р), произвольного кортежа Ь € Я и произвольных а, £ рг^т II л ¿1*4 3 £ к, Я содержит кортеж а такой, что

Ъ[г], если В £ рггЯ, а[г] = ^ с, если В С рг,Я и Ь[г] = с, 1,[г], если г £ Щ и Ь[г] £ В,

• удовлетворяет М-полуразрезающему свойству, если для любого неприводимого (n-местного) отношения R £ Inv(F) справедливо включение (ргуЛПВ^') х р Спи для любых г,] 6 U и любого (аиа:) £ prMi?nB2 найдется кортеж а £ ргу-ЙПВ^' такой, что а[г] = а„ a¡j] = а3,

• удовлетворяет свойству Ш-расширяемости, если для любого (п-местного) отношения R £ Inv(F) (a) для любого индекса к G W и любого а £ В найдется кортеж a £ R такой, что а[г] б В для всех г € W и а[/с] — а, (Ь) для любых индексов k,l е W и любой пары (о, Ъ) £ pik<[R существует а £ R такой, что а[г] £ В для всех г £ W и а[&] = a,a[í] = 6, (с) для любого кортежа а £ В^' такого, что (а[г],а[?]) £ ргг R, и для любых индексов i,j £ W найдется кортеж b £ Re условием

!а[г], если г £ W,

d, если |рггй| = 2 и {d} = рггЙП В, d, если {d} = рггп

Для 3-элементной алгебры А мы будем различать следующие 10 условий (Р1) А удовлетворяет частичному 0-свойству, (Р2) А удовлетворяет разрезающему свойству, (РЗ) А удовлетворяет (а — Ь)-заместительному свойству для 2-элементной подалгебры В такой, что а £ А — В, Ъ £ В, (Р4) А является В-прямоуголыюй для некоторой 2-элементной подалгебры В, (Р5) А удовлетворяет свойству В-полупрямоугольности для некоторой 2-элементной подалгебры В, (Р6) А удовлетворяет В-полуразрезающему свойству для некоторого 2-элементной подалгебры В и В содержит термальную функцию большинства, (Р7) А удовлетворяет свойству В-расширяемости для некоторой 2-элементной подалгебры В С А, (Р8) А имеет термальную функцию большинства, (Р9) А содержит термальную бинарную консервативную коммутативную операцию, (Р10) А содержит тер-мальн>ю мальцевскую операцию

Теорема 8. Если многообразие, порожденное идемпотентной 3-элементиой алгеброй А = (A, F) избегает тип 1, то найдется ре-дукт А' — (A, F') алгебры А, удовлетворяющий тем же условиям, и такой, что для А' выполнено одно из условий (Р1)-(Р10)

Дл каждого из условий (Р1)-(Р10) разработан полиномиальный алгоритм, решающий задачу CSP(A) для алгебр А, удовлетворяющих соответствующему условию

Теорема 9. Идемпотентная 3-элементная алгебра полиномиальна тогда и только тогда, когда она порождает многообразие, избегающее тип 1 В противном случае она NP-полна.

Хотя по теореме 4 в данном случае проблема распознавания 1М решается положительно, т е существует полиномиальный алгоритм, распознающий 3-элементные полиномиальные алгебры (модели), этот общий алгоритм весьма неэффективен. Однако, с помощью условий (Р1)-(Р10) общий алгоритм может быть значительно усовершенствован. В частности, он делает возможным практическое решение задач CSP над полиномиальными 3-элементными алгебрами

Результаты о дихотомии: копсервативные алгебры. Алгебра называется консервативной, если каждое ее подмножество является подалгеброй Алгебра называется k-консервативной, если каждое ее fc-элементное подмножество является подалгеброй Следующая теорема дает полную классификацию полиномиальных консервативных алгебр

Теорема 10. Пусть А — конечная 3-копсервативная алгебра Алгебра А полиномиальна тогда и только тогда, когда для каждого S-элемептного подмножества В алгебры А (мы полагаем В = {0,1}) существует термальная операция f алгебры А такая, что

— одна из следующих операций на В конъюнкция Л или дизъюнкция У (те полурешеточная операция), операция (x/\y)\/{y/\z)\! (z Ах) (те функция большинства), мальцевская операция х — у+z (mod 2) Во всех остальных случаях эта алгебра NP-полна

Следствие 2. Конечная 3-консервативная алгебра полиномиальна тогда и только тогда, когда она порождает многообразие, избегающее тип 1 В противном случае алгебра NP-полна

Важным частным случаем задач CSP для консервативных алгебр является Я-Раскраска графа со списками, в которой дан (ориентированный) граф G и для каждой его вершины список вершин графа Я, требуется определить, существует ли гомоморфизм из G в Н, отображающий каждую вершину G в вершину из соответствующего списка [38, 39, 40, 41] В [38, 40] было получено описание неориентированных ~графов7для которых эта задача может быть ре- -шена за полиномиальное время Можно проверить, что найденный в этих работах критерий эквивалентен наличию у Н полиморфизма, являющегося функцией большинства

Следствие 3. Пусть Н — (ориентированный) граф Задача Н-Раскраска графа со списками решаема за полиномиальное время тогда и только тогда, когда для каждого 2-элементного множества В вершин графа (мы полагаем В = {0,1}) существует консервативный полиморфизм f графа Н такой, что — одна из

следующих операций на В• конъюнкция Л или дизъюнкция У (те полурешеточная операция), операция (х Л у) V (у Л z) V (z Л х) (т е функция большинства), мальцевская операция х - у + z (mod 2) Во всех остальных случаях эта задача NP-полна

Результаты о дихотомии: алгебры с минимальным клоном термальных операций.

Теорема 11. Пусть А — конечная алгебра, клон термальных операций Term (А) которой минимален А полиномиальна, если Term(A) порожден константной операцией, функцией большинства, аффинной операцией или бинарной идемпотентной коммутативной операцией, в противном случае, т е если Term (А) порожден перестановкой, унарной операцией, действующей тождественно на своем образе, полупроекцией или бинарной идемпотентной некоммутативной операцией, А NP-полна

Идемпотентные алгебры и реберно-окрашенные графы. Три

типа операций из теоремы 10, действующих на 2-элементных подалгебрах консервативных алгебр, могут быть представлены следующим образом Элементы алгебры изображаются вершинами графа Если 2-элементная подалгебра имеет термальную полурешеточную операцию, то ее элементы соединены красным ребром В противном случае, если подалгебра имеет термальную функцию большинства, то ее элементы соединены желтым ребром Наконец, для оставшихся 2-элементных подалгебр, если найдется термальная аффинная операция, то элементы подалгебры соединяются синим ребром Полученный таким образом для алгебры А реберно-окрашенный граф будем обозначать через Q(А) Теорема 10 может быть сформулирована в терминах графа 5(A)

Следствие 4. 3-консервативная алгебра А полиномиальна тогда и только тогда, когда Q(А) является полным графом В противном случае она NP-полна

В случае произвольной идемпотентной алгебры А граф Я (А) может быть определен следующим образом Множество вершин графа

Я{А\) — это основное множество А алгебры А Пара а,Ь € А является ребром графа 9 (А) тогда и только тогда, когда существует конгруэнция 9 подалгебры (а, Ь), порожденной множеством {а,6}, и термальная операция / алгебры А такие, что либо f¡g — аффинная операция на (а,Ь)/д, либо //о — полурешеточная операция или функция большинства на {а/д, Ь/д}

Цвета (типы) ребер определим аналогично тому, как это сделано для консервативных алгебр

• Ребро аЬ красное или имеет полурешеточпый тип, если существуют конгруэнция 9 подалгебры (а, Ь) и бинарная термальная операция f алгебры А такие, что //$ — полурешеточная операция на {а/фЬ/д},

• ребро аЬ желтое или имеет мажоритарный тип, если оно не имеет полурешеточного типа и существуют конгруэнция 0 подалгебры {а, Ь) и тернарная термальная операция / алгебры А такие, что Цд~ функция большинства на {а/д,Ь/д],

• ребро аЬ синее или имеет аффинный тип, если оно не имеет полурешеточного или мажоритарного типа и существует конгруэнция в подалгебры (а, Ь) и тернарная термальная операция / алгебры А такие, что //д — аффинная операция на {а,Ь)/д

Связность графа 9(А), а также наличие ребер определенного цвета, тесно соотносятся с наличием или отсутствием простых интервалов того или иного типа в решетках конгруэнций алгебр из многообразия, порожденного А Будем говорить, что алгебра А удовлетворяет условию связности, если для любой ее подалгебры В граф 5(В) связен

Теорема 12. (1) Многообразие, порожденное конечной идемпо-тентной алгеброй А, избегает тип 1 тогда и только тогда, когда А удовлетворяет условию связности

(2) Многообразие, порожденное конечной идемпотентной алгеброй А, избегает типы 1 и 2 тогда и только тогда, когда А удовлетворяет условию связности и Я (А) не содержит ребер аффинного типа

Таким образом, гипотеза о дихотомии может быть сформулирова-

шГследающим образом идемпотентная алгебра полиномиальна то-_____

гда и только тогда, когда она удовлетворяет условию связности

Необходимость условия связности для полиномиалыюсти алгебры следует из теорем 3 и 12 Достаточность этого условия удается

доказать при некоторых условиях на граф Я(А) Каждое полурешеточное ребро аЬ графа Я (А) может быть естественным образом ориентировано пусть в и / — конгруэнция алгебры {а, Ъ) и термальная операция из определения ребер полурешеточного типа, ребро аЪ направлено от а к Ь если /(а/д,Ь/д) — Если найдутся конгру-эции и операции, свидетельствующие о различных ориентациях ребра, мы полагаем, что существует два ориентированных ребра между а и Ь, направленных в противоположные стороны Граф называется (сильно) полурешеточно связным, если любые две его вершины соединены (ориентированным) путем, состоящим из ребер полурешеточного типа Множество сильно полурешеточно связных компонент графа Я'(А) наделено частичным порядком, определенным следующим образом для компонент А, В полагаем А < В если существует ориентированный путь, состоящий из ребер полурешеточного типа, из некоторой вершины из А в какую-нибудь вершину из В

Теорема 13. Пусть А — конечная идемпотентная алгебра, удовлетворяющая условию связности и такая, что граф Я(В) содержит единственную максимальную сильно полурешеточно связную компоненту относительно порядка < для любой подалгебры В из А Тогда А полиномиальна

Алгебры ограниченной ширины. Модель А называется моделью ограниченной ширины, если существует Даталог-программа V такая, что для каждой модели В гомоморфизм из В в А существует тогда и только тогда, когда В принимается программой V Алгебра А называется алгеброй ограниченной ширины, если каждая модель из Б(;г(А) являются моделью ограниченной ширины Лароз и Задо-ри [84) показали, что для любой модели 01раниченн0й ширины А алгебра А^(.А) также имеет ограниченную ширину Они также доказали, что если идемпотентная алгебра имеет ограниченную ширину, то многообразие ею порожденное избегает типы 1 и 2 Все исследованные алгебры, порождающие многообразие, избегающее типы 1 и 2, имеют ограниченную ширину Таким образом, уместно предположить, что указанное условие является также достаточным Пункт (2) теоремы 12 позволяет сформулировать это предположение в терминах графа б (А) алгебра А имеет ограниченную ширину тогда и только тогда, когда А удовлетворяет условию связности и Я (А) не содержит синих ребер

Имеет место следующее достаточное условие ограниченности ширины алгебры

Теорема 14. Если алгебра удовлетворяет, условиям теоремы 13, то она имеет ограниченную ширину

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

Теорема 15. Пусть А — идемпотентная алгебра одного из следующих типов строго простая, 3-элементная, 3-консервативная, с минимальным клопом термальных операций Тогда А имеет ограниченную ширину тогда и только тогда, когда она удовлетворяет условию связности и Q(А) не содержит синих ребер

Алгебраический подход к задам о подсчете числа решений.

Для ограниченных задач CSP о подсчете числа решений справедлив результат, аналогичный результату Джевонса [65, 70] для задач распознавания

Теорема 16. Пусть модели Аг,Лг таковы, что Pol(_4i) С Pol (А2) Тогда задача #CSP(^2) сводима по Тьюрингу к задаче #С8Р(Лх) В частности, если #CSP(./4i) разрешима за полиномиальное время, то #CSP(yi.2) также разрешима за полиномиальное время Если #СБР(Л) #Р-полна, то #CSP(.4i) #Р-полна

Алгебра А называется #-полиномиалъной, если задача #CSP(.A) может быть решена за полиномиальное время для любой модели A е Str(A), алгебра называется #Р-полной, если задача #CSP(.A) является #Р-полпой для некоторой модели А Е Str(A)

Теорема 17. (1) Пусть А — конечная модель Тогда задача #CSP(.A) полиномиальна тогда и только тогда, когда алгебра Alg(>4) #-полиномиалъна, СБР(Л) #Р-полна тогда и только тогда, когда Alg(-Ä) #Р-полна

(2) Пусть А — конечная алгебра Если А #-полиномиальна, то любая конечная алгебра из многообразия порожденного А также #-полиномиальна Если некоторая алгебра из этого многообразия #-Р-полна, то А также #Р-полна

Подобно тому, как ключевой NP-полной задачей распознавания является /с-Раскраска графа, ключевой #Р-полной задаче о подсчёте числа решений является ftCSP(R), где R — бинарное рефлек-___

сивное не симметричное отношение Хагеманн и Мичке в [55] показали, что если конечная алгебра А не имеет мальцевской термальной

операции, то некоторая конечная алгебра из многообразия, порожденного А, имеет совместимое бинарное рефлексивное не симметричное отношение Таким образом приходим к необходимому условию #-полиномиальности

Теорема 18. Каждая конечная #-полиномиальная алгебра имеет малъцевскую операцию

Во многих классах алгебр #-полиномиальными являются в точности мальцевские алгебры В их число входят 2-элементные алгебры [17], алгебры, соответствующие графам [52], те алгебры вида (А, Pol (Л)), где R — бинарное симметричное отношение, равномерные алгебры, те алгебры, каждая конгруэнция которых имеет равное число элементов в каждом классе

Сингулярные алгебры и многообразия. Условие теоремы 18 не является достаточным условием #-полиномиальности Простейшим контрпримером является алгебра Alg(G), где G — некоторый ориентированный граф с 9 вершинами Еще одно необходимое условие #-полиномиальности доставляет следующее утверждение Пусть а, ß — отношения эквивалентности на некотором множестве, А\, , Л;., В\.. ,Bi — а- и /3-классы, соответственно Через M(a,ß) мы обозначаем матрицу (Мч) размера k х I, где Мг] = \Аг П В31

Теорема 19. Пусть а, ß — отношения эквивалентности на множестве А и А = (Л, а, ß) Задача #CSP(А) решается за полиномиальное время тогда и только тогда, когда rank(M(a,/?)) равен количеству классов в а V ß. В противном случае #СБР(Л) является фР-полной

С помощью теоремы 17 это условие может быть усилено Алгебру, любые две конгруэнции а, ß которой удовлетворяют условию rank(M(а, /3)) равен количеству классов в а V ß, назовем конгруэпц-сингулярной Многообразие называется конгруэнц-сингулярным, если любая его конечная алгебра конгруэнц-сингулярна

Следствие 5. Если алгебра А #-полиномиальна, то многообразие, ею порожденное, является конгруэнц-сингулярным

Нетрудно заметить, что каждое конгруэнц-сингулярное многообразие является конгруэнц-перестановочным, те имеет терм Мальцева

Следующая теорема полностью решает проблемы 2D и 2С Проблема 2М остается открытой

Теорема 20. Конечная алгебра #-полиномиальна тогда и только тогда, когда она порождает конгруэнц-сингулярное многообразие

Список литературы

[1] М А Всемирнов, Э А Гирш, Е Я Дандин, С В Иванов Алгоритмы для пропозициональной выполнимости и верхние оценки их сложности// Записки научных семинаров ПОМИ 2001 Т 277 С 14-46

[2] J F Allen Natural Language Understanding NY Benjamin Cummihgs, 1994

[3] A Atsenas On digraph coloring problems and treewidth duality // Proc of the 20th Annual IEEE Simp on Logic m Computer Science (Chicago, 2005) P 106-115

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

[5] J Bang-Jensen, P Hell, and G MacGilhvray The complexity of colourings by semicomplete digraphs // SIAM J of Discr Math 1988. Vol 1 P 281-289

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

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

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

[9] С Carvalho, V Dalmau, P Markovic, and M Maroti CD(4) has bounded width// CoRR, 2007, ABS/0709 1934

[10J A Chandra and P Merlin. Optimal implementation of conjunctive queries in relational data bases// STOC '77 Proc 9th Symp. on Theory of Computing, NY ACM. 1977 P 77-90

-----------[11] -V. Chandru and J N. Hooker _Extended Horn sets in prepositional

logic U J ACM 1991 Vol 38 P 205-221 [12] H Chen and V Dalmau (Smart) look-ahead arc consistency and the pursuit of CSP tractabihty // Proc 10th Int Conf

on Principles and Practice of Constraint Programming (Toronto, 2004) Berlin Springer-Verlag 2004 P. 182-196 (LNCS, Vol 3258)

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

[14] D A Cohen, P G Jeavons, and M Koubarakis Tractable disjunctive constraints // Proc 3rd Int Conf on Constraint Programming (Lmz, 1997) Berlin Springer-Verlag 1997. P 478490 (LNCS, Vol 1330)

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

[16] A G Cohn Qualitative spatial representation and reasoning techniques // Berlin Springer-Verlag 1997 LNCS Vol 1303 P 1-30

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

[18] 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)

[19] B Csakany On conservative minimal operations // Lectures in universal algebra (Szeged, 1983), Amsterdam North-Holland 1986 Colloq Math Soc Janos Bolyai 43 P 49-60

[20] V Dalrnau A new tractable class of constraint satisfaction problems // Proc 6th Int Symp on Artificial Intelligence and Math 2000 P 1-6

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

[22] V Dalmau Generalized majority-minority operations are tractable // Proc 20th IEEE Ann Symp on Logic m Computer Science (Chicago, 2005) P 438-447

[23] V Dalmau, R Gavalda, P Tesson, and T Therien Tractable clones of polynomials over semigroups // Proc 11th Int Conf on

Principles and Practice of Constraint Programming (Sitges, 2005) Berlin Springer-Verlag 2005 P. 196-210 (LNCS, Vol 3709)

[24] V Dalmau and J Pearson Set functions and width 1 problems // Proc 5th Int Conf on Constraint Programming (Alexandia, 1999) Berlin Springer-Verlag 1999 P 159-173 (LNCS Vol 1713)

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

[26] R Dechter and J Pearl Network-based heuristics for constraint satisfaction problems // Artificial Intelligence 1988 Vol 34, №1 P 1-38

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

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

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

[30] J Diaz, M Serna, and D M Thilikos Counting list H-colonngs and variants // Technical Report LSI-01-27-R, Umversitat Politécnica de Catalunya, 2001

[31] J Diaz, M Serna, and DM Thilikos Counting H-colorings of partial k-trees // Theor Comput Sci 2002 Vol 281 P 291-309

[32] Q Donner On the number of list H-colorings //J. Graph Theory 1992 Vol 16, № P 239-245

[33] M Dyer, A Frieze, and M Jerrum On counting independent sets m sparse graphs // SIAM J Comput 2002 Vol 31 P 1527-1541

[34] M Dyer, L A Goldberg, C Greenhill, and M Jerrum On the relative complexity of approximate counting problems // Proc Approximation Algorithms for Combinatorial Optimization, 3rd Int Workshop (LNCS, Vol 1913) Berlin-Springer-Verlag 2000 P 108-119

[35] M Dyer and C Greenhill The complexity of counting graph

homomorphisms j/ Random Structures and Algorithms 2000 Vol. - ----

17 P 260-289

[36] R. Fagin, P Kolaitis, L Popa, and W Tan Quasi-inverses of schema mappings // Proc 26th ACM-SIGACT-SIGART Symp on Principles of Database Systems (Beijing, 2007). P. 123-132

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

[38] T Feder and P. Hell List homomorphisms to reflexive graphs // J Combinatorial Theory Ser B 1998 Vol 72 P. 236-250

[39] T Feder, P Hell, and J Huang List homomorphisms and circular arc graphs // Cornbinatonca 1999 Vol 19 P 487-505

[40] T Feder, P Hell, and J Huang Bi-arc graphs, and the complexity of list homomorphisms // J Graph Theory 2003 Vol 42, №1 P 61-80

[41] T Feder, P. Hell, S Klem, and R Motwani List partitions // SIAM J Discr Math 2003 Vol 16 P 449-478

[42] T Feder and M Y Vardi The computational structure of monotone monadic SNP and constraint satisfaction A study through datalog and group theory // SIAM J Comput 1998 Vol 28 P 57-104

[43] M Freedman, L Lovasz, and A Schryver Reflection positivity, rank connectivity, and homomorphism of graphs // Manuscript, 2005

[44] E C Freuder Complexity of k-tree structured constraint satisfaction problems // Proc 8th National Conf on Artificial Intelligence 1990 P 4-9

[45] E C Freuder Exploiting structure in constraint satisfaction problems // Constraint Programming Berlin Springer-Verlag 1993 (NATO ASI Ser Vol 131)

[46] A Fuxman, P Kolaitis, R Miller, and W Tan. Peer data exchange // ACM Trans Database Syst. 2006 Vol 31 No 4 P 1454-1498

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

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

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

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

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

[52] C Greenhill The complexity of counting colourings and independent sets m sparse graphs and hypergraphs // Computational Complexity. 2000 Vol 9 P 52-73

[53] W Gutjahr, E Welzl, and G. Woegmger Polynomial graph colorings U Discr Appl Math 1992 Vol 35 P 29-45

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

[55] J Hagemann and A Mitschke On n-permuiable congruences // Algebra Universalis 1973 Vol 3. P 8-12

[56] P Hell Algorithmic aspects of graph homomorphisms // Survey in Combinatorics 2003 Cambridge University Press 2003 P. 239276 (London Math Soc Lect Note Ser , Vol 307)

[57] P Hell and Nesetril Graphs and homomorphisms Oxford University Press, 2004 (Oxford Lect Ser in Math and its Applications Vol 28)

[58] P Hell and J NeSetril On the complexity of H-coloring // J Combinatorial Theory, Ser B 1990 Vol 48 P 92-110

[59] P Hell, J Nesetril, and X Zhu Duality and polynomial testing of tree homomorphisms // Trans AMS 1996 Vol 348, №4 P 1281-1297

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

[61] D Hobby and R N McKenzic. The Structure of Finite Algebras ---

Providence American Mathematical Society 1988 (Contemporary Mathematics Vol 76)

[62] HB Hunt III, MV. Marathe, V Radhaknshnan, and RE Stearns The complexity of planar counting problems // SIAM J Comput 1998. Vol 27 P 1142-1167.

[63] P Idziak, P Markovic, R McKenzie, M Valeriote, and R Willard Tractabihty and learnabihty arising from algebras with few subpowers // Proc 22th IEEE Ann Symp on Logic in Computer Science (Wroclaw, 2007) P 213-224.

[64] T Jayram, P. Kolaitis, and E Vee The containment problem for real conjunctive queries with inequalities // Proc 24th ACM-SIGACT-SIG ART Symp on Principles of Database Systems (Chicago, 2006) P 80-89

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

[66] 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)

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

[68] 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 276291 (LNCS, Vol 976)

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

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

[71] 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

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

[73] 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

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

[75] 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

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

[77] E Kiss and M Valeriote On tractabihty and congruence distrzbutivity // Proc 21th IEEE Ann Symp on Logic m Computer Science (Seattle, 2006) P 221-230

[78] P Kolaitis Schema mappings, data exchange, and metadata management // Proc 24th ACM-SIGACT-SIGART Symp on Principles of Database Systems (Maryland, 2005) P 61-75

[79] P Kolaitis, J Panttaja, and W Tan The complexity of data exchange // Proc 25th ACM-SIGACT-SIGART Symp on Principles of Database Systems (Chicago, 2006) P 30-39

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

[81] L Knppahl and P Barahona Applying constraint programming to protein structure determination // Proc. 5th Int Conf on Constraint Programming Berlin-Springer-Verlag 1999 LNCS Vol 1713 P 289-302

[82] V Kumar Algorithms for constraint satisfaction problems A survey // AI Magazine 1992 Vol 13, №1 P 32-44

[83] PB LadkmandRD Maddux On binary constraint problems // J ACM 1994 Vol 41 P 435-469

[84] B Larose and L Zadori Bounded width problems and algebras // Algeb'ra Universalis. 2007 Vol. 56, №3-4 P 439-466

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

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

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

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

[89] AK Mackworth Consistency in networks of relations // Artificial Intelligence 1977 Vol 8 P 99-118

[90] A K Mackworth Constraint satisfaction // Encyclopedia of Artificial Intelligence (S C Shapiro, ed) Vol 1 NY Wiley Interscience 1992 P 285-293

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

[92] 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

[93] G McGilhvray On the complexity of colourings by vertex-transitwe and arc-transitive digraphs // SIAM J Discr. Math 1991 Vol 4 P 297-308

[94] D Mitchell Resolution and constraint satisfaction // Proc Int Conf on Principles and Practices of Constraint Programming Berlin Springer-Verlag 2003 LNCS Vol 2833 P 63-79

[95] U. Montanan. Networks of constraints Fundamental properties and applications to picture processing // Information Sciences Vol 7 P 95-132

[96] B A. Nadel Constraint satisfaction m Prolog Complexity and theory-based heuristics // Information Sciences 1995 Vol 83, №34 P 113-131

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

[98] J Nesetril and X Zhu On bounded treewidth duality of graphs // J Graph Theory 1996 Vol 23 P 151-162

[99] J Nesetnl and X Zhu On sparse graphs with given colorings and homomorphisms //J Comb Theor B 2004. Vol 90 P 161-172

[100] 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

[101] 0 Reingold Undirected st- connectivity m log-space // Technical Report TR04-094, ECCC, 2004

[102] IG Rosenberg Minimal clones I the five types // Lectures m Universal Algebra (Proc Conf Szeged 1983) Amsterdam- North-Holland 1986 P 405-427 (Colloq Math Soc. Jânos Bolyai Vol 43).

[103] B Rossman Existential positive types and preservation under homomorphisisms // Proc 20th Annual IEEE Symp on Logic m Computer Science (Chicago, 2005) IEEE Computer Society 2003 P 467-476

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

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

[106] B Szczepara Minimal clones generated by groupoids PhD thesis, Université de Montreal, 1996

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

[108] E Tsang Foundations of Constraint Satisfaction London Academic Press 1993

[109] S P. Vadhan The complexity of counting m sparse, regular and planar graphs // SIAM J Comput 2001 Vol 31, №2 P 398-427

[110] L Valiant The complexity of computing the permanent // Theor Comput Sci 1979 Vol 8 P 189-201

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

[112] P van Beek On the minimality and decomposability of row-convex constraint networks // Proc AAAI-92 (San Jose, 1992), P 447452

[113] P van~IIentenryck,-Y Deville,-and C-M -Teng - -A generic- -arc-consistency algorithm and its specializations // Artificial Intelligence 1992 Vol 57 P 291-321

[114] Т. Waldhauser Minimal clones generated by majority operations // Algebra Universalis 2000 Vol 44 No 1-2 P 15-26

Работы автора по теме диссертации

[115] A A Bulatov, PG Jeavons, and A A Krokhm Constraint satisfaction problems and finite algebras // Proc 27th Int Colloq on Automata, Languages and Programming Berlin Spnnger-Verlag 2000 P 272-282 (LNCS Vol 1853)

[116] A A Bulatov, PG Jeavons, and A A Krokhm The complexity of maximal constraint languages // Proc 33rd Ann ACM Symp on Theory of Computing (Hersomssos, 2001) ACM Press 2001 P 667-674

[117] A Bulatov and P Jeavons Algebraic structures in combinatorial problems // Technical Report Techmsche Umversitat Dresden

2001 M ATH-AL-4-2001

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

[119] A A Bulatov A dichotomy theorem for constraints on a three-element set ¡J Proc 43rd IEEE Symp. on Foundations of Computer Science (Vancouver, 2002) IEEE Computer Society

2002 P 649-658

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

[121] A A Bulatov, P G Jeavons, and A A. Krokhm 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

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

[123] 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

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

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

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

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

[128] A A Bulatov, Р G Jeavons, and A A Krokhm Classifying complexity of constraints using finite algebras // SIAM J Comput 2005 Vol 34, №3 P 720-752

[129] A Bulatov, A Krokhin and P Jeavons The complexity of constraint satisfaction An algebraic approach // Structural Theory of Automata, Semigroups and Universal Algebra (Montreal, 2003) Berlin Sprmger-Verlag 2005 P 181-213 (NATO Science Series 1Г Mathematics, Physics, and Chemistry Vol 207)

[130] Andrei A Bulatov and Martin Grohe The complexity of partition functions 11 Theor Comput Sci 2005 Vol 348, №2-3 P 148-186

[131] Andrei A Bulatov B-colormg dichotomy revisited // Theor Comput Sci 2005 Vol 349, №1 P 31-39

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

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

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

[135] Andrei A. Bulatov A dichotomy theorem for constraint satisfaction problems on a 3-element set // J ACM. 2006 Vol. 53, №1 P 66120

[136] Andrei A Bulatov and Victor Dalmau A simple algorithm for - - Mal'tsev constraints // SIAM J. Comput. 2006 Vol 36, №1 P.

16-27

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

138] А А Булатов Тождества в решетках замкнутых классов // Дискретная Математика 1992 Т 4 №4 С 140-148

139] А А Булатов Полиномиальные редукты модулей // Известия ВУЗов. Математика 1996 Т 40 №10 С 73-76

140] А А Булатов Подрешетки решетки клонов функций на 3-элементном множестве I // Алгебра и логика 1999 Т. 38, №1 С 3-23

141] А А Булатов Подрешетки решетки клонов функций па 3-элементном множестве II j j Алгебра и логика 1999 Т 38, №3 С 269-295

142] A A Bulatov, Р G Jeavons, and М V Volkov Finite semigroups imposing tractable constraints // Semigroups, Algorithms, Automata and Languages (Gracmda M S Gomes, Jean-Eric Pm, Pedro V Silva, eds ) Singapore World Scientific P 313-329

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

144] A Bulatov, F Borner, A Krokhm and P Jeavons Quantified constraints, algorithms and complexity // Proc 17th Int Workshop on Computer Science Logic (Vienna, 2003) Berlm Springer-Verlag 2003 P 58-70 (LNCS, Vol 2803)

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

146] A Atserias, A Bulatov and A Dawar Affine systems of equations and counting mfinitary logic // Proc 35th Int Colloq on Automata, Languages and Programming Berlin Springer-Verlag. 2007 P 558-570 (LNCS Vol 4596).

147] A Atserias, A Bulatov and V Dalmau On the power of Inconsistency j/ Proc 35th Int Colloq on Automata, Languages and Programming Berlin.Spnnger-Verlag 2007 P 279-290 (LNCS Vol 4596)

Подписано в печать 14 04 2008 Формат 60 х 84 1/16 _ Бумага офсетная Уел печ л 2 15 Тираж 100 Заказ Щ

Отпечатано в ИПЦ "Издательство УрГУ". 620083, г Екатеринбург, ул Тургенева, 4

Введение

В.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 Задача СЭР

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).