Сложность задачи проверки тождеств в конечных полугруппах тема автореферата и диссертации по математике, 01.01.06 ВАК РФ
|
Гольдберг, Светлана Викторовна
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Екатеринбург
МЕСТО ЗАЩИТЫ
|
||||
|
2008
ГОД ЗАЩИТЫ
|
|
01.01.06
КОД ВАК РФ
|
||
|
|
||||
На правах рукописи
ГОЛЬДБЕРГ Светлана Викторовна
СЛОЖНОСТЬ ЗАДАЧИ ПРОВЕРКИ ТОЖДЕСТВ В КОНЕЧНЫХ ПОЛУГРУППАХ
01 01 06 — математическая логика, алгебра и теория чисел
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата физико-математических наук
Екатеринбург — 2008
ооз
003169968
Работа выполнена на кафедре алгебры и дискретной математики ГОУ ВПО "Уральский государственный университет им А М Горького"
Научный руководитель:
доктор физико-математических наук, профессор M В. Волков
Официальные оппоненты доктор физико-математических
наук С И Кублановский
кандидат физико-математических наук, доцент С И Кацман
Ведущая организация
Омский государственный педагогический университет
Защита диссертации состоится "17" июня 2008 года в "dit 30' часов на заседании диссертационного совета Д 004 006 03 в Институте математики и механики УрО РАН по адресу 620219, г Екатеринбург, ул С Ковалевской, 16
С диссертацией можно ознакомиться в библиотеке Института математики и механики УрО РАН
Автореферат разослан "4£> " МоиЗ_ 2008 г
Ученый секретарь диссертационного совета,
доктор физ-мат наук
В. В Кабанов
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Тождества являются классическим объектом алгебры Изучение абстрактных свойств тождеств конечных алгебр занимает важное место в современных исследованиях Этой теме посвящено огромное число публикаций, в том числе и обобщающего характера Применительно к тождествам конечных полугрупп обстоятельный обзор накопленной информации см , например, в [5] и [21].
В последнее время во всем мире активно развиваются исследования на стыке абстрактной алгебры и теории сложности вычислений Взаимодействие этих дисциплин происходит во встречных направлениях С одной стороны, алгебраические методы оказались весьма эффективными при анализе вычислительной сложности целого класса важных для теории и приложений комбинаторных задач, а именно, обобщенных задач выполнимости (Constraint Satisfaction Problems), см , например, диссертацию Булатова [1] С другой стороны, многие алгебраические по своей сути задачи интересны с точки зрения вычислительной сложности соответствующих алгоритмов В частности, тема данной диссертации находится на стыке теории конечных полугрупп и теории сложности вычислений. Нас будет интересовать вычислительная сложность алгоритма проверки тождеств в различных конечных полугруппах
Указанная задача интересна для компьютерных наук, например, в ее связи с теорией спецификаций Под формальными алгебраическими спецификациями понимают выражения, записанные на языке, описывающем программные системы, их свойства и поведение при различных входных данных, без учета ограничений, которые могут возникнуть в результате конкретной реализации данной программной системы Подобная абстракция, не зависящая от конкретных решений реализации, делает формальные спецификации исключительно полезными при разработке программных систем, спецификации играют роль посредника между пользователями, разработчиками, тестировщиками и писателями технической документации Формальные спецификации успешно применяются в разработке сложных программных систем (см., например, [22])
Математически, формальные спецификации основаны на алгебраических понятиях - идеях и методах универсальной алгебры Взаимосвязь между реализацией программной системы и ее формальной спецификацией соответствует, если говорить в алгебраических терминах, взаимосвязи между алгеброй и множеством тождеств, в этой алгебре выпол-
ненных Таким образом, изучение вычислительной сложности проверки тождеств в алгебрах важно для исследований в теории формальных спецификаций, в том числе для построения эффективных систем проверки моделей на соответствие заявленным требованиям
Под задачей проверки тождеств в конечной алгебре понимается следующая задача распознавания, имеющая в качестве параметра заданную конечную алгебру Л:
УСЛОВИЕ, тождество рад,
ВОПРОС. Выполнено ли тождество р ~ q в алгебре Л? Задачу проверки тождеств для данной алгебры Л будем обозначать через Check-Id (Л)
Отметим, что в приведенной формулировке алгебра не включается в состав входного условия, а лишь играет роль предопределенного параметра Это означает, что при анализе вычислительной сложности задачи Check-ld(.A) размер алгебры Л считается заданной константой и ее величина не влияет на порядок сложности алгоритма
Ясно, что задача Check-ld(X) для конечных алгебр Л алгоритмически разрешима - если термы р и q в совокупности зависят от т переменных, можно просто поочередно подставлять вместо переменных всевозможные m-ки элементов алгебры А и проверять, приводят ли такие подстановки к равным значениям термов р и q Заметим, однако, что, поскольку число т-ок, подлежащих перебору, равно \Л\т, время работы такого прямолинейного алгоритма в худшем случае экспоненциально зависит от размера входных данных С другой стороны, очевидно, что для любой конечной алгебры Л задача Check-Id (Д) принадлежит классу сложности co-NP, так как ее отрицание является задачей с полиномиальной проверкой, т. е. принадлежит классу NP если для какой-то пары термов (р, q) тождество р ~ g не выполняется в алгебре Л, то недетерминированный полиномиальный алгоритм может угадать m-ку элементов из Л, опровергающую данное тождество, а затем подтвердить свою догадку вычислением значений термов р и q на этой т-ке.
Исследовать вычислительную сложность задачи Check-Id(Д) предложил М В. Сапир в хорошо известном обзоре [12] Как подмечено в [12, с. 402], если Л - двухэлементная булева алгебра, то задача Check-ld(^) равносильна отрицанию классической задачи Выполнимость. Поскольку последняя NP-полна, отсюда следует, что задача проверки тождеств в двухэлементной булевой алгебре будет co-NP-полной. Отметим, что при стандартном предположении Р Ф NP(cm [2,16]) NP-полнота и co-NP-
полнота означают, что полиномиального алгоритма для соответствующей задачи не существует
Интересно классифицировать сложность задачи проверки тождеств в различных классических конечных алгебрах, в частности в кольцах, группах и полугруппах Эта задача также отмечалась в [12] Для краткости условимся называть алгебру легкой, если задача проверки тождеств в ней решается за полиномиальное время В противном случае алгебру будем называть сложной
На сегодня полное решение задачи о проверке тождеств получен для ассоциативных колец Хант и Стирнс [10] показали, что задача СИеск-\diJZ) разрешима за полиномиальное время, если кольцо нильпотент-но, а Баррис и Лоуренс [6] установили, что эта задача со-Г\1Р-полна, если % - ненильпотентное кольцо Для групп столь же законченного описания пока нет, но недавно были получены существенные продвижения в направлении к нему Так, Баррис и Лоуренс [7] доказали полиномиальную разрешимость задачи СЬеск-1с1(£/) для случаев, когда группа 0 нильпо-тентна или диэдральна, последний результат получен также Хорватом и Сабо в [9], где установлена полиномиальная разрешимость задачи проверки тождеств и для некоторых других типов метабелевых групп С другой стороны, Хорват, Лоуренс, Мераи и Сабо [8] обнаружили, что если группа Я неразрешима, то задача СЬеск-И(5) оказывается со-1\1Р-полной.
В классе полугрупп, не являющихся группами, ситуация оказалась более запутанной Здесь до сих пор были найдены лишь отдельные примеры, в которых задача проверки тождеств со-МР-полна, см [11,13,14, 17-20] Не перечисляя все эти примеры, упомянем доказанную Вертеши и Сабо [19,20] со^Р-полноту задачи проверки тождеств для полугрупп всех 2x2 матриц над 2-элементным и 3-элементным полями, а также результат Климы [14] и Сайфа [17] о со-№Р-полноте задачи СЬесЫсД-В]) для б-элементного моноида Брандта В\ Последний результат дает, вероятно, минимальный по числу элементов пример полугруппы, для которой задача проверки тождеств является сложной с вычислительной точки зрения
Полиномиальная разрешимость задачи проверки тождеств была доказана для следующих классов полугрупп коммутативных полугрупп [13], комбинаторных (апериодических) конечных 0-простых полугрупп [18], полугрупп с единицей, содержащих менее 6 элементов [14]
Трудности в классификации конечных полугрупп с точки зрения
вычислительной сложности их задачи проверки тождеств объясняются отсутствием какой-либо сложностной "наследственности" В частности, класс полугрупп с полиномиальной проверкой тождеств незамкнут относительно взятия подполугрупп и гомоморфных образов - соответствующие примеры можно найти в работах [14,17]
Так как конечные 0-простые полугруппы играют важную роль в общей теории конечных полугрупп и возникают в качестве главных факторов в строении произвольной конечной полугруппы (см [3, §26]), то естественно было начать исследование класса всех конечных полугрупп именно с 0-простых Благодаря классической теореме Риса-Сушкевича (см [3], теорема 3 5) все конечные 0-простые полугруппы получаются с помощью конструкции регулярных рисовских полугрупп матричного типа
Регулярные рисовские полугруппы матричного типа, структурная группа которых единична, дают в точности все комбинаторные конечные 0-простые полугруппы Для таких полугрупп была установлена полиномиальная разрешимость задачи проверки тождеств [18] Кроме того, известно, что если структурная группа рисовской полугруппы матричного типа сложна, то и сама полугруппа сложна [18, предложение 5 1] Однако, оставался открытым следующий вопрос.
Вопрос 1. Существует ли пример рисовской полугруппы матричного типа, чья задача проверки тождеств не решается за полиномиальное время, в то время как задача проверки тождеств для структурной группы данной полугруппы полиномиально разрешима?
Если посмотреть на задачу классификации конечных полугрупп относительно сложности их задачи проверки тождеств несколько с другой стороны - со стороны уже известных результатов, и учесть ту роль, которую играют максимальные подгруппы при изучении строения полугруппы, представляется естественным поставить следующий вопрос
Вопрос 2. Как связаны сложность задачи проверки тождеств в конечных полугруппах со сложностью задачи проверки тождеств в конечных группахг
Кроме того, естественно попытаться классифицировать по сложности проверки тождеств некоторые наиболее важные полугруппы, такие, как полугруппы матриц над конечными полями, а также полугруппы преобразований конечных множеств
Вопрос 3. Какова сложность задачи проверки тождеств в полугруппе всех п х п-матриц над конечным полем?
Вопрос 4. Какова сложность задачи проверки тождеств в полугруппе Т(п) всех преобразований п-элементного множества?
Наряду с полугруппой всех преобразований n-элементного множества интерес представляют также и преобразования ранга не более 2 Во-первых, среди полугрупп преобразований ранга не более к полугруппа 22(71) преобразований ранга не более 2 является первым нетривиальным объектом для исследования вычислительной сложности ее задачи Check-Id, поскольку полугруппа преобразований ранга 1 является полугруппой правых нулей (при записи преобразований слева направо) и тривиальна с точки зрения проверки тождеств в ней Во-вторых, исследованию с различных точек зрения тождеств полугрупп Тг(п) посвящено немало работ, см например, [4,5,15] Было естественным продолжить серию этих исследований изучением вычислительной сложности задачи Check-ld(T2(n))
Вопрос 5. Какова сложность задачи проверки тождеств в полугруппе Тг(п) всех преобразований п-элементного множества с не более чем 2-элементным образом?
Целью работы является получение ответов на поставленные вопросы 1-5
Научная новизна. Все результаты диссертации являются новыми Новыми являются и некоторые методы, использованные при получении результатов
Теоретическая и практическая ценность. Диссертационная работа носит теоретический характер Полученные результаты могут быть использованы в теории полугрупп, универсальной алгебре и в теоретических компьютерных науках
Апробация результатов работы. Основные результаты диссертации докладывались на Международной алгебраической конференции, посвященной 250-летию Московского университета и 75-летию кафедры высшей алгебры (Москва, 2004), Международной алгебраической конференции, посвященной 100-летию со дня рождения П Г Конторовича и 70-летию JI. Н Шеврина (Екатеринбург, 2005), Международной конференции по вычислительным и алгоритмическим аспектам теории по-
лугрупп (Сэнт-Эндрюс, Шотландия, 2006), Мальцевских чтениях (Новосибирск, 2006), Международной конференции по сложности алгоритмов в универсальных алгебрах (Сегед, Венгрия, 2007), заседании семинара "Алгебраические системы" (УрГУ)
Публикации. Основные результаты диссертации опубликованы в работах [23-28], работа [25] опубликована в журнале, входившем на момент публикации в список ведущих рецензируемых научных журналов, определенном ВАК
Три публикации по теме диссертации являются совместными с В. Вер-теши В тезисах докладов [23] анонсированы результаты статей [25,26] Результаты работы [26] были получены в нераздельном соавторстве В работе [25] В Вертеши была предложена графовая задача, с помощью которой интерпретируется задача проверки тождеств в построенной 19-элементной 0-простой полугруппе, доказательство со-ЫР-полноты задачи проверки тождеств было проведено диссертантом.
Публикации [24,27] являются совместными с Ж. Алмейдой и М В. Волковым В тезисах докладов [24] был анонсирован один из результатов работы [27] - редукционная теорема о сводимости задачи проверки тождеств в максимальных подгруппах конечной полугруппы к задаче проверки тождеств в самой полугруппе Этот результат был получен в нераздельном соавторстве Результат работы [27] о задаче проверки тождеств в полной полугруппе преобразований п-элементного множества принадлежит диссертанту.
Работа [28] является совместной с М В Волковым, идея доказательства была предложена М В Волковым, а реализована диссертантом
Структура и объем диссертации. Диссертация состоит из введения, четырех глав и списка литературы Объем диссертации составляет 72 страницы, библиография содержит 57 наименований.
КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обсуждается история вопроса, даются определения и формулируются основные результаты работы.
В главе 1 строится 19-элементная полугруппа М - пример сложной рисовской полугруппы матричного типа с легкой структурной группой В § 1 1 доказываются некоторые свойства построенной полугруппы. В § 1 2 приводятся необходимые для дальнейшего доказательства определения и результаты теории графов В § 1 3 доказывается, что построенная полугруппа обладает минимальным числом элементов среди всех
сложных 0-простых полугрупп В § 1 4 описывается построение графов по сэндвич-матрице рисовской полугруппы и по тождеству В этом же параграфе определяются новые графовые задачи, которые позволили перевести задачу проверки тождеств на язык гомоморфизмов графов. В §1,5 формулируются необходимые и достаточные условия выполнения тождества в построенной полугруппе Далее в § 1.6 условия выполнения тождества переводятся на графовый язык и определяются преобразования над графами тождеств, не влияющие на выполнимость тождеств в полугруппе М В § 1 7 доказывается полиномиальная сводимость промежуточной графовой задачи к задаче проверки тождеств в полугруппе М. Там же описан полиномиальный от числа вершин входного графа алгоритм, строящий по данному двудольному графу граф с равными степенями соответствующих вершин в долях, используя всего две операции перестановку вершин в долях и приписывание существующим ребрам дополнительной кратности И наконец, в § 1 8 окончательно доказывается со-МР-полнота задачи СЬеск-1с((Л^) благодаря полиномиальной сводимости промежуточных графовых задач к известной ^-полной задаче о ретракции графов В § 1 9 отмечается, что полугруппа М. может быть представлена с помощью преобразований 3-элементного множества как факторполугруппа Риса Т2(3)/71(3) по идеалу Тх(ш) - полугруппы преобразований ранга 1, и строится соответствующий изморфизм
Глава 2 посвящена сведению изучения задачи проверки тождеств в конечных полугруппах к изучению задачи проверки тождеств в их максимальных подгруппах Глава 2 не дробится на параграфы в ней приводится и сама редукционная теорема, и полученное следствие, полностью характеризующее сложность проверки тождеств в полугруппе всех п х п-матриц над конечными полями
В 3 главе диссертации рассматривается полная полугруппа преобразований п-элементного множества Данная глава также не разбита на параграфы.
В главе 4 рассматривается полугруппа преобразований п-элементного множества ранга не более 2 В § 4 1 строится полиномиальный алгоритм проверки тождеств при пф 3, ав§42 доказывается со^Р-полнота задачи проверки тождеств при п = 3
Нумерация теорем, лемм, предложений и следствий двойная Первое число соответствует номеру главы, второе - номеру утверждения
Глава 1 диссертации посвящена ответу на Вопрос 1. Искомой стала 19-
элементная рисовская полугруппа матричного типа М. = М°(С2) I, Л, Р) над 2-элементной группой С2 = {а, е} (е - это единица и а2 = е) и с сэндвич-матрицей
Легкость проверки тождеств в структурной группе полугруппы М довольно очевидна. В диссертации доказывается, что проверка тождеств в самой полугруппе, тем не менее сложна
К сожалению, исчерпывающей сводимости рассмотрения сложности задачи Check-Id для конечных полугрупп к их главным факторам, 0-простым полугруппам, не существует Этот вывод можно сделать на основании того, что существуют такие полугруппы, у которых все главные факторы имеют полиномиально разрешимую задачу проверки тождеств, но сама полугруппа тем не менее сложна (см. [11]).
Основным результатом главы 2 является следующая редукционная теорема
Теорема 2.1. Пусть S - конечная полугруппа, a Q - прямое произведение всех ее максимальных подгрупп Существует полиномиальное сведёте задачи Check-Id(G) к задаче Check-ld(S)
Отсюда и из уже упомянутого результата работы [8] о неразрешимых группах немедленно вытекает
Следствие 2.1. Если конечная полугруппа содержит неразрешимую подгруппу, то задача проверки тождеств в этой полугруппе co-NP-полна
Обращение следствия 2 1 неверно - среди полугрупп с co-NP-полной задачей проверки тождеств имеются и такие, в которых все подгруппы тривиальны Таким примером является б-элементный моноид Брандта В\, чьи максимальные подгруппы одноэлементны
Однако, комбинируя следствие 2 1с известными результатами, можно полностью классифицировать полугруппы некоторых важных типов по отношению к сложности проверки тождеств Например, для полугрупп матриц над конечными полями исчерпывающий ответ дает
Следствие 2.2. Задана проверки тождеств в полугруппе всех тг х п-матриц над конечным полем со-МР-полма при п > 1 и решается за полиномиальное время при п = 1
Тем самым, мы ответили на поставленный Вопрос 3
В главе 3 изучается сложность задачи проверки тождеств для полной полугруппы преобразований п-элементного множества При п > 5 здесь также можно использовать следствие 2.1, но случай п < 4 требует другого подхода Нам удалось получить следующий "почти полный" результат
Теорема 3.1. Задача проверки тождеств в полугруппе всех преобразований п-элементного множества со-Г\1Р-псмна при п = 3ип>5и решается за полиномиальное время при п — 1,2
Вопрос о сложности проверки тождеств в полугруппе всех преобразований 4-элементного множества пока остается открытым Отметим, что не исключено, что и в этом случае можно будет воспользоваться сведением из теоремы 1, так как, хотя группа всех перестановок 4-элементного множества и разрешима, она не попадает ни в один из известных классов групп с полиномиальной проверкой тождеств
Если же рассматривать не все преобразования, а лишь преобразования ранга не более 2, то ситуация с разделением полугрупп на легкие и сложные оказывается несколько неожиданной Главным результатом главы 4 является следующая теорема
Теорема 4.1. Задача проверки тождеств в полугруппе Тг(п) всех преобразований п-элементного множества ранга не более 2 является полиномиально разрешимой при п^З и со-ЫР-полной при п = 3.
Доказательство со-Г\1Р-полноты задачи проверки тождеств в полугруппе Тг(3) основано на полиномиальном сведении к ней задачи СЬеск-1с1(Т2(3)/Т1(3)), со-ЫР-полнота которой прежде доказывается в главе 1
Автор выражает глубокую благодарность своему научному руководителю профессору М В Волкову за постановки задач и постоянное внимание к работе
Список литературы
[1] А А Булатов. Алгебраические методы в иследовании комбинаторных задач// Диссертация на соискание ученой степени доктора физ -мат наук 2008
[2] М. Гэри, Д. Джонсов Вычислительные машины и труднорешаемые задачи// М. Мир, 1982
[3] А Клиффорд, Г Престон Алгебраическая теория полугрупп// Том 1 М : Мир, 1972
[4] Н Г Торлопова О полугруппах ранга 2// 1982 Деп в ВИНИТИ
[5] Л Н Шеврин, М В Волков Тождества полугрупп// Известия вузов Математика 1989 №11
[6] S Burris, J Lawrence The equivalence problem for finite rings// J Symbolic Comput 1993 V 15 №1. P. 67-71
[7] S Burris, J Lawrence Results on the equivalence problem for finite groups// Algebra Universalis 2005 V 52 №4 P 495-500
[8] G Horvath, J Lawrence, L. Merai, Cs Szabo. The complexity of the equivalence problem for nonsolvable groups// В печати
[9] G Horvath, Cs. Szabo The complexity of checking identities over finite groups// Int J Algebra and Computation 2006 V 16 JV«5 P 931-939
[10] H В Hunt III, R E Stearns The complexity of equivalence for commutative rings// J. Symbolic Comput 1990 V. 10 №5 P 411-436.
[11] M. Jackson, R McKenzie Interpreting graph colorability m finite semigroups// Int. J Algebra and Computation 2006 V 16 №1 P 119-140
[12] О G Kharlampovich, M V Sapir Algorithmic problems in varieties// Int J Algebra and Computation 1995. V 5 №4-5 P 379-602
[13] A Kisielewicz Complexity of semigroup identity checking// Int J. Algebra and Computation 2004 V 14 №4 P 455-464
[14] О Klima. Complexity issues of checking identities m finite monoids// В печати
[15] G. Mashevitzky. On finite basis problem for left hereditary systems of identities/ в кн. J. Almeida, G.MS Gomes, P V Silva, Semigroups, automata and languages World Scientific, 1996 P 167-181.
[16] С H Papadimitriou Computational Complexity// Reading-Menlo Park-N Y Addison-Wesley Publishing Company, 1994.
[17] S Self. The Perkins semigroup has co-NP-complete term-equivalence problem// Int J. Algebra and Computation. 2005 V 15 №2 P 317326.
[18] S Seif, Cs. Szabo Computational complexity of checking identities in 0-simple semigroups and matrix semigroups over finite fields// Semigroup Forum. 2006 V 72 №2 P 207-222
[19] Cs Szabo, V Vertesi The complexity of the word-problem for finite matrix rings// Proc. Amer. Math. Soc 2004 V 132 №12. P 3689-3695
[20] Cs Szabo, V Vertesi The complexity of checking identities for finite matrix rings// Algebra Universalis. 2004. V. 51 №4. P. 439-445
[21] M. V. Volkov The finite basis problem for finite semigroups// Mathe-matica Japonica 2001 V 53 №1. P 171-199
[22] J. Wing. A specifier's introduction to formal methods// Computer. 1952 V 23. P 8-24
Работы автора по теме диссертации
[23] S V. Plescheva, V Vertesi Complexity of the identity checking problem for finite 0-simple semigroups// Междунар алгебраич конф , посвященная 250-летию Московского университета Тезисы докладов М Изд-во МГУ, 2004 С 249-250
[24] J Almeida, S V Plescheva, M V. Volkov An application of group generic implicit operators to the complexity of identity checking m finite semigroups// Междунар алгебраич. конф , посвященная столетию со дня рождения П Г Конторовича и 70-летию JI Н. Шеврина Тезисы докладов Екатеринбург Изд-во Урал ун-та, 2005 С 16-17
[25] С В Плещева, В Вертеши. Сложность задачи проверки тождеств в одной конечной 0-простой полугруппе// Изв Урал гос. ун-та 2006 №43 С. 72-102
[26] S.V.Plescheva, V.Vertesi. Azonossagok 0-egyszeru felcsoportokban// Mathematikai Lapok 2007 № 2 С 54-75 (На венгерском)
[27] J Almeida, S V Plescheva, M V Volkov Complexity of the identity checking problem for finite semigroups// Preprint, 2007-19 Centro de Matematica Porto: Universidade do Porto, 2007
[28] S V.Goldberg, M V Volkov Complexity of variety membership for non-fimtely based finite semigroups// Международная конференция "Algorithmic complexity and universal algebra" Тезисы докладов Издательство ун-та Сегеда, 2007 С 3
Ризография НИЧ ГОУ ВПО УГТУ-УПИ 620002, г Екатеринбург, ул. Мира 19
Введение
0.1 Алгебра, алгоритмы и сложность.
0.2 Предварительные сведения.
0.3 Проблема проверки тождеств в алгебрах.
0.4 Задача проверки тождеств для конечных полугрупп.
0.5 Постановка задач.
0.6 Результаты диссертации
0.7 Апробация результатов.
0.8 Список обозначений.
1 Пример 0-простой полугруппы с co-NP-полной задачей проверки тождеств
1.1 Некоторые свойства полугруппы М.
1.2 Необходимые сведения о задачах на графах.
1.3 Минимальность Л4 среди сложных 0-простых полугрупп
1.4 Графовые конструкции в задаче Check-ld(.M).
1.5 Условия выполнения тождества в полугруппе Л4.
1.6 Взаимосвязь задач Check-ld(Al) и BEven-Hom(iiex).
1.7 Сведение задачи BEven-Hom(ffea;) к задаче Check-Id(Л4)
1.8 Взаимосвязь задачи о ретракции графов, задачи Even-Hom и задачи BEven-Hom.
1.9 Представление полугруппы Л4 с помощью преобразований 3-элементного множества.
2 Сведение задачи проверки тождеств в полугруппах к задаче проверки тождеств в группах
3 Сложность проверки тождеств в полной полугруппе преобразований
4 Сложность проверки тождеств в полугруппе преобразований ранга
4.1 Легкость проверки тождеств в 22(77.) при пф 3.
4.2 Сложность проверки тождеств в Т2(3).
0.1 Алгебра, алгоритмы и сложность
Сама наука алгебра в свое время возникла как алгоритмическая дисциплина, призванная упорядочить и объединить методы решения возникавших задач. И в современном мире приложения алгебры как в других областях математики, так и за пределами математики чаще всего связаны с алгоритмическими аспектами. Теме алгоритмических проблем в алгебре посвящено на сегодняшний день большое число публикаций. Важные работы на эту тему были выполнены в научной школе JI.H. Шеврина: см., например, обзор О.Г. Харлампович и М.В. Сапира по алгоритмическим проблемам в многообразиях [27] и диссертацию В.Ю. Попова [8].
Если до недавнего времени конечной точкой исследования алгоритмических задач было установление их разрешимости или неразрешимости, то возникшая в 1970-х годах формализация сложности алгоритмов открыла большой горизонт для дальнейшего изучения алгоритмически разрешимых задач. Теория вычислительной сложности началась с работ Кука [18], Левина [5] и Карпа [26] и сразу же набрала грандиозную скорость своего развития, благодаря как открывшимся теоретическим перспективам, так и существенной потребности практиков в исследовании реальных возможностей алгоритмов. Общее представление о теории вычислительной сложности можно получить из классических учебников [2] и [36].
Применительно к обсуждавшейся области обнаружилось, что многие базовые алгоритмические задачи алгебры, разрешимость которых давно известна и/или очевидна, приводят к интересным и зачастую весьма трудным проблемам, если задаться вопросом о вычислительной сложности соответствующих алгоритмов. С одной стороны, интересен непосредственно слож-ностный анализ алгебраических алгоритмов. С другой стороны, если решается задача, в которой алгебра или класс алгебр выступают в качестве входного параметра, то интересно изучить взаимосвязь сложности соответствующего алгоритма и строения алгебры (класса алгебр) и тем самым, возможно, классифицировать алгебры по сложности рассматриваемой задачи.
В качестве примера упомянем следующую задачу Var-Memb (необходимые определения можно найти в §0.2): для двух конечных алгебр Л и В одинаковой сигнатуры определить, удовлетворяет ли алгебра Л всем тождествам алгебры В. (Обозначение Var-Memb произведено от 'Variety membership", поскольку в терминах теории многообразий речь идет о распознавании принадлежности алгебры Л многообразию, порожденному алгеброй В). Понятно значение задачи Var-Memb для современной универсальной алгебры, в которой, как хорошо известно, классификация алгебр с помощью тождеств занимает одно из центральных мест. Алгоритмическая разрешимость задачи Уаг-МетЬ легко выводится из НБР-теоремы Тарского и отмечалась еще в пионерской работе Калицкого [25]. Исследование же вычислительной сложности этой задачи началось сравнительно недавно и принесло довольно неожиданные результаты. Верхнюю оценку привели Бергман и Слуцки [13], установившие, что задача \/аг-МетЬ принадлежит классу 2-ЕХРТ1МЕ (класс задач, разрешимых за дважды экспоненциальное время). Эта оценка сперва представлялась сильно завышенной, но затем Секели [46] показал, что обсуждаемая задача N Р-трудна, а на конференции в Сегеде в 2007 Козик анонсировал (см. [32]) пример алгебры с 2-ЕХРТ1МЕ-полной задачей Уаг-МетЬ, тем самым доказав точность оценки 2-ЕХРТ1МЕ.
Задача, рассматриваемая в настоящей работе, в определенном смысле еще более фундаментальна, чем задача Уаг-МетЬ. В последней спрашивается, удовлетворяет ли алгебра Л каждому из (бесконечно многих) тождеств алгебры В, в то время как здесь мы локализуем ситуацию, спрашивая, выполняется ли в фиксированной конечной алгебре Л одно данное тождество. Соответствующую задачу будем называть задачей проверки тождеств в алгебре Л и обозначать через СЬеск-1с1(Л).
Указанная задача интересна для компьютерных наук, например, в ее связи с теорией спецификаций. Под формальными алгебраическими спецификациями понимают выражения, записанные на языке, описывающем программные системы, их свойства и поведение при различных входных данных, без учета ограничений, которые могут возникнуть в результате конкретной реализации данной программной системы. Подобная абстракция, не зависящая от конкретных решений реализации, делает формальные спецификации исключительно полезными при разработке программных систем: спецификации играют роль посредника между пользователями, разработчиками, те-стировщиками и писателями технической документации. Формальные спецификации успешно применяются в разработке сложных программных систем (см., например, [49]).
Математически, формальные спецификации основаны на алгебраических понятиях - идеях и методах универсальной алгебры. Взаимосвязь между реализацией программной системы и ее формальной спецификацией соответствует, если говорить в алгебраических терминах, взаимосвязи между алгеброй и множеством тождеств, в этой алгебре выполненных. Таким образом, изучение вычислительной сложности проверки тождеств в алгебрах важно для исследований в теории формальных спецификаций, в том числе для построения эффективных систем проверки моделей на соответствие заявленным требованиям.
Дадим теперь строгое определение. Под задачей проверки тождеств в конечной алгебре понимается следующая задача распознавания, имеющая в качестве параметра заданную конечную алгебру Л:
УСЛОВИЕ: тождество р — q;
ВОПРОС: Выполнено ли тождество p — q в алгебре Л?
Отметим, что в приведенной формулировке алгебра не включается в состав входного условия, а лишь играет роль предопределенного параметра. Это означает, что при анализе вычислительной сложности задачи Check-Id (Д) размер алгебры Л считается заданной константой и ее величина не влияет на порядок сложности алгоритма.
Как видно из названия, тема данной диссертации находится на стыке теории конечных полугрупп и теории сложности вычислений. А именно, пас будет интересовать вычислительная сложность алгоритма проверки тождеств в различных конечных полугруппах. Хочется отметить, что исследования на стыке абстрактной алгебры и теории сложности вычислений в последнее время активно развиваются во всем мире. Взаимодействие этих дисциплин происходит во встречных направлениях. С одной стороны, как уже упоминалось выше, многие алгебраические по своей сути задачи интересны с точки зрения вычислительной сложности соответствующих алгоритмов. С другой стороны, алгебраические методы оказались весьма эффективными при анализе вычислительной сложности целого класса важных для теории и приложений комбинаторных задач, а именно, обобщенных задач выполнимости (Constraint Satisfaction Problems), см., например, диссертацию А.А.Булатова [1].
0.2 Предварительные сведения Предварительные сведения из универсальной алгебры
Под тождеством в алгебре Л понимается пара термов р и q, записанных в сигнатуре этой алгебры. Тождество записывается посредством формального равенства p — q. Алгебра Л удовлетворяет тождеству p — q, или тождество p — q выполнено в этой алгебре, если при любой подстановке вместо переменных тождества элементов алгебры тождество получается верное равенство. Последнее означает, что для любого гомоморфизма tp : С1 Л, где - алгебра всех термов соответствующей сигнатуры над множеством переменных термов р и q, выполняется pep — qip.
С понятием тождества связано и такое важное для универсальной алгебры понятие как многообразие универсальных алгебр. Напомним, что класс алгебр К, называется многообразием, если существует такой набор тождеств Т, что К, - это в точности все алгебры, удовлетворяющие тождествам множества Т. С другой стороны, класс алгебр К. называется многообразием, если этот класс замкнут относительно взятия подалгебр, гомоморфных образов и прямых произведений. Эквивалентность этих двух определений была доказана Биркгофом (см., например, [14, теорема 11.9]).
Пусть дана алгебра Л. Под многообразием, порожденным алгеброй Л (классом алгебр /С), понимается класс всех таких алгебр, которые удовлетворяют всем тождествам, выполненным в алгебре Л (в классе /С). Классическая теорема Тарского дает конструктивный подход к порожденным многообразиям.
Предложение 0.1 (НБР-теорема Тарского). Пусть дан класс алгебр /С. Пусть МБР (1С) есть класс алгебр, полученный из 1С как результат последовательного применения операторов Н, Б, Р - соответственно "взятия гомоморфных образов", "взятия подалгебр" и "взятия прямых произведений". Тогда многообразие, порожденное классом /С, совпадает с НБР(7С).
Предварительные сведения из теории сложности вычислений
В теории вычислительной сложности под задачами подразумевают так называемые массовые задачи, задаваемые своими УСЛОВИЕМ и ВОПРОСОМ и объединяющие в себе множество конкретных задач. Каждая конкретизация подобной массовой задачи получается фиксированием УСЛОВИЯ. Размером задачи обычно называют каким-то образом измеренный размер входного УСЛОВИЯ - можно считать, что это длина записи УСЛОВИЯ на ленте машины Тьюринга.
Задача принадлежит классу Р, если она решается за полиномиальное от размера УСЛОВИЯ время на детерминированной машине Тьюринга (см. [2,36]). С практической точки зрения именно такие задачи можно назвать "легкими" по временным затратам. Задача принадлежит классу ЫР, если она решается за полиномиальное время на недетерминированной машине Тьюринга. Если угадав каким-то образом ответ задачи, мы можем за полиномиальное время на детерминированной машине Тьюринга этот ответ проверить, то задача называется задачей с полиномиальной проверкой. Все задачи с полиномиальной проверкой, очевидно, принадлежат классу ЫР. Задача принадлежит классу со-МР, если ее отрицание принадлежит классу ЫР.
В диссертации для оценки временной сложности задач будет неоднократно использоваться сведение заведомо сложных задач к исследуемым нами задачам. Именно такой разработанный в 1970-х годах подход позволил формально доказывать вычислительную сложность задач. Дадим строгое определение.
Задача А полиномиально сводится к задаче В (обозначение А>р В), если существует полиномиальный (от размера задачи А) алгоритм /, который по любой конкретизации а задачи А строит конкретизацию /(а) задачи В так, что ответ на а положителен тогда и только тогда, когда ответ на /(а) также положителен.
Отметим, что в диссертации мы будем рассматривать именно полиномиальную сводимость задач. Такой вид сводимости был применен в 1972 году в пионерской работе Карпа для доказательства сводимости задачи Выполнимость к задаче Гамильтонов путь - поиска гамильтонова пути в графе.
Напомним, что под задачей Выполнимость понимается следующая комбинаторная задача распознавания:
УСЛОВИЕ: булева формула Ф(£ь., хп), записанная в конъюнктивной нормальной форме (как конъюнкция дизъюнкций переменных или их отрицаний);
ВОПРОС: существует ли для переменных . ,хп такое истинностное означивание, что Ф(х\,., хп) становится истиной?
Задача называется N Р [со- !\1Р]-трудной, если к ней полиномиально сводится любая задача из класса МР[со-1\1Р].
При (естественном с практической точки зрения) предположении, что Р^ИР, именно такие задачи являются плохо (не полиномиально) вычислимыми на практике.
Задача называется NР[со-N Р]-полной, если она принадлежит классу МР [со-1\1Р] и при этом N Р [со- N Р] -трудна.
Независимо полученный Куком и Левиным результат о ЫР-полноте задачи Выполнимость позволил с тех пор доказать вычислительную сложность (МР или со-ЫР-полноту) широкого класса алгоритмических задач.
Кроме классов Р, ЫР и со-МР, рассматривают и другие классы вычислительной сложности. Например, говорится, что задача принадлежит классу ЕХРТ1МЕ, если эта задача может быть решена на детерминированной машине Тьюринга за экспоненциальное (вида 2пС) время, где п - это размер входного УСЛОВИЯ. Если задача решается лишь за дважды экспоненциальное время, то говорят, что она принадлежит классу 2-ЕХРТ1МЕ. Несложно понять, что любая задача из класса ЫР может быть решена на детерминированной машине Тьюринга за экспоненциальное время (если организовать полный перебор). Следовательно,
Р С МР С ЕХРТ1МЕ С 2-ЕХРТ1МЕ.
Предварительные сведения из теории полугрупп
Введем несколько необходимых для дальнейшего понятий из теории полугрупп.
Как обычно, через й"1 мы будем обозначать наименьшую полугруппу с единицей, содержащую данную полугруппу Б (т.е. Б1 — ¿>, если в <!э есть единица, а в противном случае в1 = 5и{1}, где добавленный символ 1 ведет себя как единица по умножению).
Напомним, что полугруппа называется простой, если она не содержит собственных двусторонних идеалов. Полугруппа ¿> с нулем 0 называется 0-простой, если (1) в2 ф 0 и (11) 0 есть единственный собственный двусторонний идеал из 5. Конечные 0-простые полугруппы являются вполне 0-простыми.
Благодаря следующей классической теореме Риса-Сушкевича все конечные 0-простые полугруппы можпо изучать, используя довольно ясную матричную конструкцию.
Предложение 0.2 ( [4], теорема 3.5). Полугруппа вполне 0-проста тогда и только тогда, когда она изоморфна регулярной рисовской полугруппе матричного типа над группой с нулем.
Опишем конструкцию рисовских полугрупп матричного типа над группами с нулем. Пусть О - группа и О0 = С?и 0 - группа с нулем, полученная из (? присоединением нуля 0. Пусть Р - произвольная, но фиксированная матрица над Через Ли/ обозначим множества, индексирующие соответственно строки и столбцы матрицы Р. Через обозначим элемент матрицы Р, стоящий на пересечении строю! с номером Л 6 Л и столбца с номером г £ I. Рассмотрим множество Б, состоящее из символа 0 и всех троек вида (г, д, А), где д £ С, г £ I, А £ Л. Зададим умножение на элементах множества Б по следующим правилам:
Легко проверить, что заданное таким образом умножение ассоциативно, а значит 5 становится полутруппой. Она называется рисовской полугруппой матричного типа с сэндвич-матрицей Р над группой с нулем и обозначается через «М°((7; /, А; Р). Группа О называется структурной группой полугруппы Л4°.
Следующее классическое утверждение связывает понятие регулярности для рисовской полугруппы со строением ее сэндвич-матрицы. Напомним, что элемент а полугруппы 5 называется регулярным, если а £ аБщ полутруппа называется регулярной, если каждый ее элемент регулярен.
Предложение 0.3 ( [4], лемма 3.1). Рисовская полугруппа матричного типа регулярна тогда и только тогда, когда ее сэндвич-матрица содержит по крайней мере один ненулевой элемент в каждой строке и в каждом столбце. а • 0 = 0 • о = 0 для всех а £ Б если рф 0; если = 0.
Матрицы, упомянутые в предложении, называются регулярными. Регулярные рисовские полугруппы матричного типа, чья структурная группа единична, дают в точности все комбинаторные (апериодические) конечные 0-простые полугруппы.
На каждой полугруппе Б могут быть определены три естественных пред-порядка <с, <ц и - отношения левой, правой и двусторонней делимости: а <с Ь а = вЬ для некоторого я 6 51; а <тг Ь а — Ьв для некоторого в е 51; % а <у Ь -Ф^ а = вЫ для некоторых з, £ е 5й.
Через С, 72. и 3 обозначаются отношения эквивалентности, соответствующие предпорядкам <£, <л и <J (т.е. аСЪ тогда и только тогда, когда а <с Ь <с а, и т.д.). Объединение отношений эквивалентности £ и 11 обозначается через V, а пересечение - через Отношения ¿7", "О и К называются отношениями Грина. Они играют важную роль при изучении строения полугрупп. Хорошо известно, что в любой конечной полугруппе отношения J и V совпадают.
Кроме того, напомним два элементарных факта из теории полугрупп, доказательства которых можно найти, например, в [38, глава 3], см. там предложение 1.4 и следствие 1.7.
Предложение 0.4. Пусть Б - конечная полугруппа, в, £ £ >5.
1) Если з <ct и в Л, то в а.
2) Если в <з в2, то %-класс элемента я является максимальной подгруппой полугруппы 5.
В случае вполне 0-простых полугрупп известно, что отношение % является конгруэнцией (см. теорему 2.52 в [4]), следовательно для любой вполне 0-простой полугруппы Б мы можем корректно определить факторполугруп-пу Б/Н. Для рисовской полугруппы матричного типа ¿> = I, Л; Р) подполугруппу Б/Н можно мыслить как объединение нуля и всех пар вида (г, А), где г € /, А £ Л, с сэндвич-умножением посредством матрицы Р', полученной из Р заменой всех ее ненулевых элементов на 1. Таким образом, Б/Ц = .Л40({1}; I, Л; Р') - рисовская полугруппа матричного типа над единичной группой с 0-1 сэндвич-матрицей.
Обозначим полугруппу всех преобразований на множестве X через Т(Х). Напомним, что образом преобразования (р 6 Т(Х) называется множество
1т</2 = {х(р, х € X}, а ядром - разбиение кег <р, определенное следующим образом: х (кег ф) у (ж, у £ X), если х<р = у (р.
Мощность множества Im ip называется рангом преобразования (р. В случае \Х\ = п полугруппу всех преобразований n-элементного множества обозначим через Т{п). Через ТГ(Х) [соответственно Тг(гг)] будем обозначать множество всех таких преобразований из Т(Х) [соответственно Т(п)], образ которых состоит из не более г элементов.
Мы будем записывать преобразования справа от аргумента; произведение двух преобразований - это результат их последовательного выполнения в том порядке, в котором они записаны. Отметим, что на сложность задачи проверки тождеств это соглашение не влияет, - полугруппа ^Цп) всех преобразований n-элементного множества, действующих справа налево, ан-тиизоморфна Т(п) и удовлетворяет некоторому тождеству тогда и только тогда, когда в Т(п) выполняется зеркальное отражение этого тождества. (Все утверждения, в том числе из работ других авторов, мы будем формулировать в терминах преобразований, действующих слева направо.)
Кроме всего прочего, в данной диссертации нас будут интересовать фак-торполугруппы Риса вида Tr(n)/Tri(n) по идеалу Tr-i(n). Напомним определение.
Пусть I - идеал полугруппы S. Определим отношение р на S, полагая apb (a, b е S) тогда и только тогда, когда либо а — Ь, либо а и b принадлежат I. Отношение р называется конгруэнцией Риса по модулю I. Классами эквивалентности полутруппы S по модулю р являются само I и каждое одноэлементное множество {а}, где а G S \ I. Вместо S/p пишется S/I и S/I называется факторполугруппой Риса полугруппы S по модулю I. Можно представлять себе S/I как результат сжатия I в один элемент (нуль), в то время как элементы из S \ I не затрагиваются.
В ходе работы нам будет полезна информация о Х>-строении полугруппы преобразований Т(Х) и полугруппы Мп{Т) всех п х n-матриц над полем Т. Соответствующие результаты хорошо известны и могут быть найдены, например, в книге [4], но для полноты изложения мы сформулируем их в явном виде.
Предложение 0.5 ( [4], теорема 2.9). (1) Существует такое взаимно однозначное соответствие между множеством всех Т>-классов полугруппы Т(Х) и множеством всех кардинальных чисел г < \Х\, что Т>-класс Dr, соответствующий г, состоит из всех элементов полугруппы Т(Х), ранг которых равен г.
2) Пусть г ~ кардинальное число < \Х\. Существует такое взаимно однозначное соответствие между мнооюеством всех С-классов, содержащихся в Д, и множеством всех подмножеств У мощности г из X, что С-класс, соответствующий множеству У, состоит их всех элементов полугруппы Т{Х), для которых У является образом.
3) Пусть г - кардинальное число < |Х|. Существует такое взаимно однозначное соответствие между мноэ1сеством всех И-классов, содержащихся в Д, и множеством всех разбиений 7г множества X, для которых |Х/7г| = г, что И-класс, соответствующий к, состоит из всех элементов полугруппы Т(Х), ядро которых совпадает с 7Г.
4) Пусть г - кардинальное число < |Х|. Существует такое взаимно однозначное соответствие между множеством всех %-классов, содержащихся в Д, и множеством всех пар (тг,У), где ж есть разбиение множества X, а У - подмножество мнооюества X, причем |Х/7г| = |У| = г, что %-класс, соответствующий (тг,Х), состоит из всех элементов полугруппы Т{Х), для которых ядро совпадает с к, а образ - с У.
Из того, что множество Д = Тг(п) \ Тг1(п) является Т'-классом полугруппы Т(п), в частности, следует, что факторполугруппа Риса Тг (п)/Тг-1 (п) является 0-простой полутруппой.
В качестве иллюстрации к предложению 0.5 приведем 2>-строение полугруппы Т(3). Полугруппа Т(3) имеет три V-класса: класс Д} есть ни что иное, как симметрическая группа 5з, класс £>2 состоит из всех преобразований ранга 2 и класс Д = 3). Будем нумеровать строки разбиениями множества {1,2,3}, а столбцы - подмножествами множества {1,2,3}. Опустим Дь который состоит из одного К-класса, совпадающего с группой <5з.
Дг {13} {23} {12}
13}{2} /123\ VI31 У» Ыз/ /123\ /123\ 4232/' (323/ /1234
1}{23} \}ПЗ/ ' ии/ /123\ /123\ ШЯЯ \322/ /1234 /1'23\ ЧЖ/' \211 /
12}{3} V113/ ' \331/ Щ № N223/' (зз2/ Щ Щ \112Л \221 /
А {1} {2} Г- СО
123} о /Ш\ 1222) /123у (333/
Полугруппу Мп(Р) можно себе представлять как полугруппу всех линейных преобразований п-мерного векторного пространства V над полем Т. Для полугруппы Мп{Т) выполняются все условия предложения 0.5 для
Х| = {1,., n}, если заменить "подмножество Y множества X" на "подпространство W пространства V", мощность множества У на dim W, "разбиение 7г множества X" на "подпространство N пространства V" и |-Х"/тг| на dim (V/N).
0.3 Проблема проверю! тождеств в алгебрах
Ясно, что задача СИеск-И(Л) для конечных алгебр Л алгоритмически раз-репшма - если термы ридв совокупности зависят от т переменных, можно просто поочередно подставлять вместо переменных всевозможные m-ки элементов алгебры А и проверять, приводят ли такие подстановки к равным значениям термов р и д. Заметим, однако, что, поскольку число m-ок, подлежащих перебору, равно |Д|т, время работы такого прямолинейного алгоритма в худшем случае экспоненциально зависит от размера входных данных. С другой стороны, очевидно, что для любой конечной алгебры А задача Check-Id (Л) принадлежит классу сложности co-NP, так как ее отрицание является задачей с полиномиальной проверкой, т. е. принадлежит классу NP: если для какой-то пары термов (р, q) тождество р — q не выполняется в алгебре А, то недетерминированный полиномиальный алгоритм может угадать m-ку элементов из А, опровергающую данное тождество, а затем подтвердить свою догадку вычислением значений термов р и q на этой т-ке.
Исследовать вычислительную сложность задачи Check-ld(^) предложил Сапир в хорошо известном обзоре [27]. Как подмечено в [27, с. 402], если А -двухэлементная булева алгебра, то задача Check-Id^) равносильна "отрицанию" классической задачи Выполнимость. Поскольку последняя NP-полна, отсюда следует, что задача проверки тождеств в двухэлементной булевой алгебре будет co-NP-полной.
Интересно классифицировать сложность задачи проверки тождеств в различных классических конечных алгебрах, в частности в кольцах, группах и полутруппах. Эта задача также отмечалась в [27]. Для краткости условимся называть алгебру легкой, если задача .проверки тождеств в ней решается за полиномиальное время. В противном случае алгебру будем называть сложной.
На сегодня полный ответ получен для ассоциативных колец: Хант и Стирнс [23] показали, что задача Check-Id(1Z) разрешима за полиномиальное время, если кольцо TZ нильпотентно, а Баррис и Лоуренс [15] установили, что эта задача co-NP-полна, если 1Z — ненильпотентное кольцо.
При доказательстве данного результата тождества над кольцом рассматривались как пара термов, однако если изначально расписать каждый терм как сумму одночленов (раскрыв произведение сумм), то размер задачи существенно изменится и, соответственно, может измениться и вычислительная сложность проверки тождеств. Поясним на примере. Многочлен (х + у)п как терм можно записать в виде (х + у)(х + у) • ■ • (х + у) и тогда размер этого многочлена оценится как on, однако записав этот многочлен в виде суммы одночленов хп+хп~1у+хп~2у2+. .+уп, мы тут же получаем его размер равным п2п. Подобная разница существенна при оценке сложности задачи, т. к. может привести к понижению сложности самого алгоритма относительно увеличенного размера входного условия. Поэтому для колец формулируется Е-версия задачи проверки тождеств, в которой на вход подается кольцевое тождество, записанное как сумма одночленов. Тем не менее, и для этой версии задачи проверки тождеств в конечных кольцах удалось получить теорему дихотомии.
Предложение 0.6 ( [45]). Пусть дано конечное кольцо 1Z. Через J(7£) обозначим радикал Докекобсона этого кольца. Тогда Т,-версия задачи проверки тождеств в кольце 7Z полиномиально разрешима, если фактор-кольцо TZ/J(TZ) коммутативно, и co-NP-полна в противном случае.
Для групп столь же законченного описания пока нет, но недавно были получены существенные продвижения в направлении к нему. Так, Баррис и Лоуренс [16] доказали полиномиальную разрешимость задачи Check-ld(^) для случаев, когда группа Q нильпотентна или диэдральна; последний результат получен также Хорватом и Сабо в [22], где установлена полиномиальная разрешимость задачи проверки тождеств и для некоторых других типов метабелевых групп. С другой стороны, Хорват, Лоуренс, Мераи и Сабо [21] обнаружили, что если группа Q неразрешима, то задача Check-Id(Q) оказывается co-NP-полной.
Отметим, что результат о сложности проверки тождеств в неразрешимых группах был анонсирован Лоуренсом еще в 2002 году и с тех пор не раз цитировался в работах на тему сложности Check-Id в конечных алгебрах. Однако, позже в доказательстве Лоуренса была найдена ошибка, которая была исправлена только в уже упомянутой работе [21].
Предложение 0.7. Пусть дана конечная группа Q. Если Q неразрешима, то Check-ld(G) co-NP-полна. Если Q нильпотентна или диэдральна, то Check-ld(Q) имеет полиномиальный алгоритм.
В классе полугрупп, не являющихся группами, ситуация оказалась более запутанной.
0.4 Задача проверки тождеств для конечных полугрупп
Исследование тождеств в классе конечных полугрупп занимает одно из центральных мест в общей теории полугрупп и этой тематике посвящено огромное число публикаций, в том числе и обобщающего характера, см., например, обзоры [11] и [48]. Изучение задачи проверки тождеств в конечных полугруппах с точки зрения ее вычислительной сложности естественным образом продолжает эту тему.
Исследования начались с построения М.В.Волковым и В.Ю.Поповым [39] в 2001 году примера полутруппы порядка < 21700, для которой задача Check-Id является co-NP-полной. Фактически, именно этот результат, доложенный Волковым на конференции по универсальной алгебре в Нэшвиле в 2002 году, спровоцировал активную исследовательскую деятельность в области сложности проверки тождеств.
В результате были построены примеры полугрупп гораздо меньшего порядка, см. [24,29,41,43,44]. Например, Сабо и Вертеши нашли первые примеры сложных матричных полутрупп:
Предложение 0.8 ( [43,44]). Задача проверки тождеств co-NP-полна для полугруппы всех 2x2 матриц над 2-элементным полем и для полугруппы всех 2x2 матриц над 3-элементным полем.
В работе [24] был построен пример 55-элементной полутруппы Б(Сз) по
5-вершинному 3-раскрашиваемому графу Сз, для которой была доказана со-NP-полнота задачи СЬеск-1с1(5'(Сз)). Для доказательства использовалась NP-полнота задачи о 3-раскраске графов.
Следующий результат, независимо полученный Климой [29] и Сайфом [41], дает, вероятно, минимальный по числу элементов пример полугруппы, для которой задача проверки тождеств является сложной с вычислительной точки зрения.
Предложение 0.9. Задача проверки mootcdecme является co-NP-полной для
6-элементпого моноида Брандта
Напомним, что моноид Брандта можно задать присоединением единицы к рисовской полугруппе матричного типа с нулем над единичной группой
G = {1} с сэндвич-матрицей Р =
В работе Сабо и Сайфа [42] была доказана наследуемость сложности задачи проверки тождеств в рисовской полугруппе матричного типа от сложности проверки тождеств в ее структурной группе.
1 0 0 1
Предложение 0.10 ( [42], предложение 5.1). Пусть дана рисовская полугруппа матричного типа Б над группой С?. Тогда если задача проверки тоо1сдеств со-ЫР-полна в группе (?, то и задача СИеск-1в(8) co-NP-noлua.
Полиномиальная разрешимость задачи проверки тождеств была доказана для следующих классов полутрупп: коммутативных полугрупп [28], ри-совских полугрупп матричного типа над единичной группой [42], полугрупп с единицей, содержащих менее б элементов [29].
Классификация конечных полугрупп с точки зрения вычислительной сложности их задачи проверки тождеств затрудняется отсутствием достаточной сложностной "наследственности". В частности, класс полугрупп с полиномиальной проверкой тождеств незамкнут относительно взятия подполугрупп и гомоморфных образов - соответствующие примеры можно найти в работах [29,41]. Мы приведем здесь один пример полугруппы с легкой задачей проверки тождеств, которая и содержит сложную подполугруппу, и имеет гомоморфный образ на сложную полугруппу.
Будем обозначать через А\ моноид, полученный присоединением единицы к рисовской полугруппе матричного типа с нулем над единичной группой
Несложно доказать (и соответствующие рассуждения можно найти в работе [42], см. там теорему 4.6), что задача СЬеск-1с1(Л2) полиномиально разрешима. Кроме того, хорошо известно, что моноид В\ принадлежит многообразию, порожденному моноидом А\ (см., например, лемму 4 в [29]). Следовательно, набор тождеств для рассматриваемой полугруппы А\ х В\ и моноида А\ совпадает, откуда немедленно следует полиномиальная разрешимость задачи СЬеск-1с1(^42х Щ)- При этом, моноид Брандта В\ является и подполугруппой полугруппы А\ х В\, и ее гомоморфным образом.
Напоследок отметим, что, конечно же, классические алгебры не ограничиваются кольцами, группами и полугруппами. Однако, нам на сегодняшний день не известны работы по исследованию сложности задачи проверки тождеств даже в таких естественных алгебрах, как решетки или алгебры Ли.
Так как конечные 0-простые полугруппы играют важную роль в общей теории конечных полугрупп и возникают в качестве главных факторов в строении произвольной конечной полутруппы (см. [4, §2.6]), то естественно было начать исследование класса всех конечных полутрупп именно с 0-простых.
Как было упомянуто в § 0.4, для комбинаторных конечных 0-простых полутрупп была установлена полиномиальная разрешимость задачи проверки
0.5 Постановка задач тождеств. Кроме того, благодаря предложению 0.10, было известно, что если структурная группа рисовской полугруппы матричного типа сложна, то и сама полугруппа сложна. Однако, оставался открытым следующий вопрос:
Вопрос 1. Существует ли пример рисовской полугруппы матричного типа, чья задача проверки тождеств не решается за полиномиальное время, в то время как задача проверки тождеств для структурной группы данной полугруппы полиномиально разрешима?
Если посмотреть на задачу классификации конечных полутрупп относительно сложности их задачи проверки тождеств несколько с другой стороны - со стороны уже известных результатов, и учесть ту роль, которую играют максимальные подгруппы при изучении строения полугруппы, представляется естественным поставить следующий вопрос:
Вопрос 2. Как связаны сложность задачи проверки тождеств в конечных полугруппах со сложностью задачи проверки тождеств в конечных группах?
Кроме того, естественно попытаться классифицировать по сложности проверки тождеств некоторые классические типы полутрупп, такие, как, например, полутруппы матриц над конечными полями, а также полугруппы преобразований конечных множеств.
Вопрос 3. Какова сложность задачи проверки тождеств в полугруппе всех п х п-матриц над конечным полем?
Вопрос 4. Какова сложность задачи проверки тождеств в полугруппе Т(п) всех преобразований п-элементного множества?
Наряду с полугруппой всех преобразований n-элементного множества интерес представляют также и преобразования ранга не более 2. Во-первых, среди полугрупп преобразований ранга не более к полугруппа Т2(п) является первым нетривиальным объектом для исследования вычислительной сложности ее задачи Check-Id, поскольку полугруппа преобразований ранга 1 является полугруппой правых нулей (при записи преобразований слева направо) и тривиальна с точки зрения проверки тождеств в ней. Во-вторых, исследованию с различных точек зрения тождеств полугрупп Тг(гг) посвящено немало работ. Описание тождеств полутруппы Т(2) можно найти в работе [11], описание тождеств полугруппы Т2(п) для п > 5 получено в работе [10]. Проблеме конечного базиса тождеств для полугруппы Т2(п) при п > 5 посвящена работа [33]. В работе [34] получено описание тождеств для полугруппы преобразований 4-элементного множества ранга не более 2 и доказано, что данная полугруппа не имеет конечного базиса своих тождеств.
Было естественным продолжить серию этих исследований изучением вычислительной сложности задачи СНеск-И(Т2(п)).
Вопрос 5. Какова сложность задачи проверки тождеств в полугруппе Т2(п) всех преобразований п-элементного множества с не более чем 2-элементным образом?
Основные результаты диссертации дают ответы на поставленные вопросы
1-5. Нумерация теорем, лемм, предложений и следствий двойная. Первое число соответствует номеру главы, второе - номеру утверждения.
1. А. А. Булатов. Алгебраические методы в иследовании комбинаторных задач// Диссертация на соискание ученой степени доктора физ.-мат.наук. 2008.
2. М. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи// М.: Мир, 1982.
3. М. И. Каргаполов, Ю. И. Мерзляков. Основы теории групп// М.: Наука, 1972.
4. А.Клиффорд, Г.Престон. Алгебраическая теория полугрупп// Том 1. М.: Мир, 1972.
5. Л. Левин. Проблемы передачи информации. 1973.
6. Р.Линдон, П.Шупп. Комбинаторная теория групп// М.: Мир, 1980.
7. Машевицкий Г. И. О тождествах в многообразиях вполне простых полугрупп над абелевыми группами // Современ. алгебра. 1978. С. 81-89.
8. В. Ю. Попов Алгоритмические проблемы для многообразий полугрупп, моноидов, групп и колец //Диссертация на соискание ученой степени доктора физ.-мат. наук. 2002.
9. Е.П. Симельгор. Тождества в конечной симметрической полутруппе// Современ. алгебра. 1974. Т. 1. С. 174-188.
10. Н.Г. Торлопова. О полугруппах ранга 2// 1982. Деп. в ВИНИТИ.
11. Л.Н.Шеврнн, М.В.Волков. Тождества полугрупп// Известия вузов. Математика. 1985. №11.
12. J. Almeida, М. V. Volkov. Subword complexity of profinite words and subgroups of free profinite semigroups// Int. J. Algebra and Computation. 2006. V. 16. №2. P. 221-258.
13. C. Bergman, G. Slutzki. Complexity of some problems concerning varieties and quasi-varieties of algebras// SIAM J. Comput. 2000. V.30. №2. P. 359382.
14. S. Burris, H. P. Sankappanavar. A Course in Universal Algebra // SpringerVerlag, 1981.
15. S. Burris, J. Lawrence. The equivalence problem for finite rings// J. Symbolic Comput. 1993. V. 15. №1. P. 67-71.
16. S. Burris, J. Lawrence. Results on the equivalence problem for finite groups// Algebra Universalis. 2005. V.52. №4. P. 495-500.
17. Buki J., Szabo Cs. Colored homomorphisms for direct products of graphs // Information Processing Letters. 2002. Vol.81, №4. P. 175-178.
18. Cook S. A., The complexity of theorem proving procedures // Proc. 3rd Ann. ACM Symp. Theory of Computing. 1971. P. 151-158.
19. С. C. Edmunds. On certain finitely based varieties of semigroups// Semigroup Forum. 1977. V. 15. №1. P. 21-39.
20. Feder Т., Hell P., Huang J. List homomorphisms and circular arc graphs // Combinatorica. 1999. Vol. 19. P. 487-505.
21. G. Horvath, J. Lawrence, L. Mdrai, Cs. Szabd. The complexity of the equivalence problem for nonsolvable groups// В печати.
22. G. Horvath, Cs. Szabo. The complexity of checking identities over finite groups// Int. J. Algebra and Computation. 2006. V. 16. №5. P. 931-939.
23. H. B. Hunt III, R. E. Stearns. The complexity of equivalence for commutative rings// J. Symbolic Comput. 1990. V. 10. №5. P. 411-436.
24. M.Jackson, R.McKenzie. Interpreting graph colorability in finite semigroups// Int. J. Algebra and Computation. 2006. V. 16. №1. P. 119-140.
25. J. Kalicki. On comparison of finite algebras// Proc. Amer. Math. Soc. 1952. V.3. №1. P. 36-40.
26. R. M. Karp. Reducability among combinatorial problems // Complexity of Computer computations, NY:1972. P.85-103.
27. O. G. Kharlampovich, M. V.Sapir. Algorithmic problems in varieties// Int. J. Algebra and Computation. 1995. V. 5. №4-5. P. 379-602.
28. A. Kisielewicz. Complexity of semigroup identity checking// Int. J. Algebra and Computation. 2004. V. 14. №4. P. 455-464.
29. O.Klima. Complexity issues of checking identities in finite monoids// В печати.
30. O.Klfma. Complexity of checking identities in monoids of tranformations// Рукопись. 2007.
31. M. Kozik, On Some Complexity Problems in Finite Algebras// PhD Dissertation. 2004. Vanderbilt University, Nashville.
32. M. Kozik. Varietal membership problem and alternation// Международная конференция "Algorithmic complexity and universal algebra". Тезисы докладов. Издательство ун-та Сегеда, 2007. С. 8.
33. G. Mashevitzky. On finite basis problem for left hereditary systems of identities/ в кн. J.Almeida, G.M.S.Gomes, P.V.Silva, Semigroups, automata and languages. World Scientific, 1996. P. 167-181.
34. G. Mashevitzky. Bases of identities of semigroups of a bounded rank transformations of a set// Рукопись. 2007.
35. Mashevitzky G. On the finite basis problem for completely 0-simple semigroup identities // Semigroup Forum. 1999. Vol. 59. №2. P. 197-219.
36. С. H. Papadimitriou. Computational Complexity// Reading-Menlo Park-N.Y.: Addison-Wesley Publishing Company, 1994.
37. Petrich M. Produit cartésien de demi-groupes complètement simples // C. R. Acad. Sci. Paris. 1964. Vol. 259. P. 277-279.
38. J-E. Pin. Varieties of Formal Languages// Oxford: North Oxford Academic and N.Y.: Plenum, 1986.
39. Popov V. Yu., Volkov M. V. Complexity of checking identities and quasi-identities in finite semigroups// Рукопись. 2001.
40. Rasin V. V. On the lattice of varieties of completely simple semigroups // Semigroup Forum. 1979. Vol.17. №2. P. 113-122.
41. S. Seif. The Perkins semigroup has co-NP-complete term-equivalence problem// Int. J. Algebra and Computation. 2005. V. 15. №2. P. 317-326.
42. S.Seif, Cs.Szabô. Computational complexity of checking identities in 0-simple semigroups and matrix semigroups over finite fields// Semigroup Forum. 2006. V. 72. №2. P. 207-222.
43. Cs. Szabô, V. Vértesi. The complexity of the word-problem for finite matrix rings// Proc. Amer. Math. Soc. 2004. V. 132. №12. P. 3689-3695.
44. Cs. Szabô, V. Vértesi. The complexity of checking identities for finite matrix rings// Algebra Universalis. 2004. V.51. №4. P. 439-445.
45. Cs. Szabô, V. Vértesi. The identity checking problem in finite rings// В печати.
46. Z. Székely. Computational complexity of the finite algebra membership problem for varieties// Int. J. Algebra and Computation. 2002. V. 12. № 6. P. 811823.
47. P. Tesson. Computational Complexity Questions Related to Finite Monoids and Semigroups. PhD Thesis. 2003. McGill University, Montréal.
48. M. V. Volkov. The finite basis problem for finite semigroups// Mathematica Japonica. 2001. V.53. №1. P. 171-199.
49. J. Wing. A specifier's introduction to formal methods// Computer. 1952. V. 23. P. 8-24.
50. S. V. Plescheva, V. Vértesi. Complexity of the identity checking problem for finite 0-simple semigroups// Междунар. алгебраич. конф., посвященная 250-летию Московского университета. Тезисы докладов. М.: Изд-во МГУ, 2004. С. 249-250.
51. С. В. Плещева, В. Вертеши. Сложность задачи проверки тождеств в одной конечной 0-простой полугруппе// Изв. Урал. гос. ун-та. 2006. №43. С.72-102.
52. S. V. Plescheva, V. Vértesi. Azonossâgok 0-egyszerù félcsoportokban// Math-ematikai Lapok. 2007. № 2. C. 54-75. (На венгерском)
53. J. Almeida, S. V. Plescheva, M. V. Volkov. Complexity of the identity checking problem for finite semigroups// Preprint, 2007-19 Centro de Matematica. Porto: Universidade do Porto, 2007.
54. S. V. Goldberg, M. V. Volkov. Complexity of variety membership for non-finitely based finite semigroups// Международная конференция "Algorithmic complexity and universal algebra". Тезисы докладов. Издательство ун-та Сегеда, 2007. С. 3.
55. С. В. Гольдберг. Сложность проверки тождеств в полугруппах преобразований ранга 2// Изв. Урал. гос. ун-та. 2008. №62. С. 24-35.
56. С. В. Гольдберг: Сложность проверки тождеств в полугруппах преобразований ранга 2// Междунар. алгебраич. конф., посвященная столетию со дня рождения А. Г. Куроша. Тезисы докладов. М.: Изд-во МГУ, 2008.
