Введение к работе
Актуальность темы. Тождества являются классическим объектом алгебры. Изучение абстрактных свойств тождеств конечных алгебр занимает важное место в современных исследованиях. Этой теме посвящено огромное число публикаций, в том числе и обобщающего характера. Применительно к тождествам конечных полугрупп обстоятельный обзор накопленной информации см., например, в [5] и [21].
В последнее время во всем мире активно развиваются исследования на стыке абстрактной алгебры и теории сложности вычислений. Взаимодействие этих дисциплин происходит во встречных направлениях. С одной стороны, алгебраические методы оказались весьма эффективными при анализе вычислительной сложности целого класса важных для теории и приложений комбинаторных задач, а именно, обобщенных задач выполнимости (Constraint Satisfaction Problems), см., например, диссертацию Булатова [1]. С другой стороны, многие алгебраические по своей сути задачи интересны с точки зрения вычислительной сложности соответствующих алгоритмов. В частности, тема данной диссертации находится на стыке теории конечных полугрупп и теории сложности вычислений. Нас будет интересовать вычислительная сложность алгоритма проверки тождеств в различных конечных полугруппах.
Указанная задача интересна для компьютерных наук, например, в ее связи с теорией спецификаций. Под формальными алгебраическими спецификациями понимают выражения, записанные на языке, описывающем программные системы, их свойства и поведение при различных входных данных, без учета ограничений, которые могут возникнуть в результате конкретной реализации данной программной системы. Подобная абстракция, не зависящая от конкретных решений реализации, делает формальные спецификации исключительно полезными при разработке программных систем: спецификации играют роль посредника между пользователями, разработчиками, тестировщиками и писателями технической документации. Формальные спецификации успешно применяются в разработке сложных программных систем (см., например, [22]).
Математически, формальные спецификации основаны на алгебраических понятиях - идеях и методах универсальной алгебры. Взаимосвязь между реализацией программной системы и ее формальной спецификацией соответствует, если говорить в алгебраических терминах, взаимосвязи между алгеброй и множеством тождеств, в этой алгебре выпол-
ненных. Таким образом, изучение вычислительной сложности проверки тождеств в алгебрах важно для исследований в теории формальных спецификаций, в том числе для построения эффективных систем проверки моделей на соответствие заявленным требованиям.
Под задачей проверки тождеств в конечной алгебре понимается следующая задача распознавания, имеющая в качестве параметра заданную конечную алгебру А:
УСЛОВИЕ: тождество р ~ q;
ВОПРОС: Выполнено ли тождество р ~ q в алгебре Л?
Задачу проверки тождеств для данной алгебры Л будем обозначать через Check-Id (Л).
Отметим, что в приведенной формулировке алгебра не включается в состав входного условия, а лишь играет роль предопределенного параметра. Это означает, что при анализе вычислительной сложности задачи Скіеск-И(Л) размер алгебры А считается заданной константой и ее величина не влияет на порядок сложности алгоритма.
Ясно, что задача Check-Id (А) для конечных алгебр А алгоритмически разрешима - если термы р и q в совокупности зависят от т переменных, можно просто поочередно подставлять вместо переменных всевозможные m-ки элементов алгебры А и проверять, приводят ли такие подстановки к равным значениям термов р и q. Заметим, однако, что, поскольку число т-ок, подлежащих перебору, равно \А\т, время работы такого прямолинейного алгоритма в худшем случае экспоненциально зависит от размера входных данных. С другой стороны, очевидно, что для любой конечной алгебры А задача Check-Id (Л) принадлежит классу сложности co-NP, так как ее отрицание является задачей с полиномиальной проверкой, т.е. принадлежит классу NP: если для какой-то пары термов (р, q) тождество р ~ q не выполняется в алгебре А, то недетерминированный полиномиальный алгоритм может угадать m-ку элементов из А, опровергающую данное тождество, а затем подтвердить свою догадку вычислением значений термов р и q на этой т-ке.
Исследовать вычислительную сложность задачи Скіеск-Н(Л) предложил М. В. Сапир в хорошо известном обзоре [12]. Как подмечено в [12, с.402], если А - двухэлементная булева алгебра, то задача СІіеск-И(Л) равносильна отрицанию классической задачи Выполнимость. Поскольку последняя NP-полна, отсюда следует, что задача проверки тождеств в двухэлементной булевой алгебре будет co-NP-полной. Отметим, что при стандартном предположении Р ф 1\1Р(см. [2,16]) NP-полнота и co-NP-
полнота означают, что полиномиального алгоритма для соответствующей задачи не существует.
Интересно классифицировать сложность задачи проверки тождеств в различных классических конечных алгебрах, в частности в кольцах, группах и полугруппах. Эта задача также отмечалась в [12]. Для краткости условимся называть алгебру легкой, если задача проверки тождеств в ней решается за полиномиальное время. В противном случае алгебру будем называть сложной.
На сегодня полное решение задачи о проверке тождеств получено для ассоциативных колец: Хант и Стирнс [10] показали, что задача Check-ld(7) разрешима за полиномиальное время, если кольцо 1Z нильпотент-но, а Баррис и Лоуренс [6] установили, что эта задача co-NP-полна, если 1Z - ненильпотентное кольцо. Для групп столь же законченного описания пока нет, но недавно были получены существенные продвижения в направлении к нему. Так, Баррис и Лоуренс [7] доказали полиномиальную разрешимость задачи Check-Id (Су) для случаев, когда группа Q нильпо-тентна или диэдральна; последний результат получен также Хорватом и Сабо в [9], где установлена полиномиальная разрешимость задачи проверки тождеств и для некоторых других типов метабелевых групп. С другой стороны, Хорват, Лоуренс, Мераи и Сабо [8] обнаружили, что если группа Q неразрешима, то задача Check-ld(^) оказывается co-NP-полной.
В классе полугрупп, не являющихся группами, ситуация оказалась более запутанной. Здесь до сих пор были найдены лишь отдельные примеры, в которых задача проверки тождеств co-NP-полна, см. [11,13,14, 17-20]. Не перечисляя все эти примеры, упомянем доказанную Вертеши и Сабо [19,20] co-NP-полноту задачи проверки тождеств для полугрупп всех 2x2 матриц над 2-элементным и 3-элементным полями, а также результат Климы [14] и Сайфа [17] о co-NP-полноте задачи Check-ldf^) для 6-элементного моноида Брандта В\. Последний результат дает, вероятно, минимальный по числу элементов пример полугруппы, для которой задача проверки тождеств является сложной с вычислительной точки зрения.
Полиномиальная разрешимость задачи проверки тождеств была доказана для следующих классов полугрупп: коммутативных полугрупп [13], комбинаторных (апериодических) конечных 0-простых полугрупп [18], полугрупп с единицей, содержащих менее б элементов [14].
Трудности в классификации конечных полугрупп с точки зрения
вычислительной сложности их задачи проверки тождеств объясняются отсутствием какой-либо сложностной "наследственности". В частности, класс полугрупп с полиномиальной проверкой тождеств незамкнут относительно взятия подполугрупп и гомоморфных образов - соответствующие примеры можно найти в работах [14,17].
Так как конечные 0-простые полугруппы играют важную роль в общей теории конечных полугрупп и возникают в качестве главных факторов в строении произвольной конечной полугруппы (см. [3, 2.6]), то естественно было начать исследование класса всех конечных полугрупп именно с 0-простых. Благодаря классической теореме Риса-Сушкевича (см. [3], теорема 3.5) все конечные 0-простые полугруппы получаются с помощью конструкции регулярных рисовских полугрупп матричного типа.
Регулярные рисовские полугруппы матричного типа, структурная группа которых единична, дают в точности все комбинаторные конечные 0-простые полугруппы. Для таких полугрупп была установлена полиномиальная разрешимость задачи проверки тождеств [18]. Кроме того, известно, что если структурная группа рисовской полугруппы матричного типа сложна, то и сама полугруппа сложна [18, предложение 5.1]. Однако, оставался открытым следующий вопрос:
Вопрос 1. Существует ли пример рисовской полугруппы матричного типа, чья задача проверки тождеств не решается за полиномиальное время, в то время как задача проверки тождеств для структурной группы данной полугруппы полиномиально разрешима?
Если посмотреть на задачу классификации конечных полугрупп относительно сложности их задачи проверки тождеств несколько с другой стороны - со стороны уже известных результатов, и учесть ту роль, которую играют максимальные подгруппы при изучении строения полугруппы, представляется естественным поставить следующий вопрос:
Вопрос 2. Как связаны сложность задачи проверки тождеств в конечных полугруппах со сложностью задачи проверки тождеств в конечных группах?
Кроме того, естественно попытаться классифицировать по сложности проверки тождеств некоторые наиболее важные полугруппы, такие, как полугруппы матриц над конечными полями, а также полугруппы преобразований конечных множеств.
Вопрос 3. Какова сложность задачи проверки тождеств в полугруппе всех п х п-матриц над конечным полем?
Вопрос 4. Какова сложность задачи проверки тождеств в полугруппе Т(п) всех преобразований п-элементного множества?
Наряду с полугруппой всех преобразований n-элементного множества интерес представляют также и преобразования ранга не более 2. Во-первых, среди полугрупп преобразований ранга не более к полугруппа Т2(п) преобразований ранга не более 2 является первым нетривиальным объектом для исследования вычислительной сложности ее задачи Check-Id, поскольку полугруппа преобразований ранга 1 является полугруппой правых нулей (при записи преобразований слева направо) и тривиальна с точки зрения проверки тождеств в ней. Во-вторых, исследованию с различных точек зрения тождеств полугрупп Т2Іп) посвящено немало работ, см. например, [4,5,15]. Было естественным продолжить серию этих исследований изучением вычислительной сложности задачи Check-ld(T2(n)).
Вопрос 5. Какова сложность задачи проверки тождеств в полугруппе Т2(п) всех преобразований п-элементного множества с не более чем 2-элементным образом?
Целью работы является получение ответов на поставленные вопросы 1-5.
Научная новизна. Все результаты диссертации являются новыми. Новыми являются и некоторые методы, использованные при получении результатов.
Теоретическая и практическая ценность. Диссертационная работа носит теоретический характер. Полученные результаты могут быть использованы в теории полугрупп, универсальной алгебре и в теоретических компьютерных науках.
Апробация результатов работы. Основные результаты диссертации докладывались на Международной алгебраической конференции, посвященной 250-летию Московского университета и 75-летию кафедры высшей алгебры (Москва, 2004), Международной алгебраической конференции, посвященной 100-летию со дня рождения П. Г. Конторовича и 70-летию Л. Н. Шеврина (Екатеринбург, 2005), Международной конференции по вычислительным и алгоритмическим аспектам теории по-
лугрупп (Сэнт-Эндрюс, Шотландия, 2006), Мальцевских чтениях (Новосибирск, 2006), Международной конференции по сложности алгоритмов в универсальных алгебрах (Сегед, Венгрия, 2007), заседании семинара "Алгебраические системы" (УрГУ).
Публикации. Основные результаты диссертации опубликованы в работах [23-28]; работа [25] опубликована в журнале, входившем на момент публикации в список ведущих рецензируемых научных журналов, определенном ВАК.
Три публикации по теме диссертации являются совместными с В. Вер-теши. В тезисах докладов [23] анонсированы результаты статей [25,26]. Результаты работы [26] были получены в нераздельном соавторстве. В работе [25] В. Вертеши была предложена графовая задача, с помощью которой интерпретируется задача проверки тождеств в построенной 19-элементной 0-простой полугруппе; доказательство co-NP-полноты задачи проверки тождеств было проведено диссертантом.
Публикации [24,27] являются совместными с Ж. Алмейдой и М.В. Волковым. В тезисах докладов [24] был анонсирован один из результатов работы [27] - редукционная теорема о сводимости задачи проверки тождеств в максимальных подгруппах конечной полугруппы к задаче проверки тождеств в самой полугруппе. Этот результат был получен в нераздельном соавторстве. Результат работы [27] о задаче проверки тождеств в полной полугруппе преобразований n-элементного множества принадлежит диссертанту.
Работа [28] является совместной с М.В. Волковым; идея доказательства была предложена М.В. Волковым, а реализована диссертантом.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав и списка литературы. Объем диссертации составляет 72 страницы, библиография содержит 57 наименований.
Похожие диссертации на Сложность задачи проверки тождеств в конечных полугруппах
