Исследуется сложность задачи проверки тождеств в конечных решетках. Показано, что тождества, обе части которых представлены в виде суммы одночленов, можно проверить за время, полиномиальное от размера тождества, в любой конечной решетке, а задача проверки тождеств, у которых в виде суммы одночленов представлена только одна часть, является co-NP-полной для любой неодноэлементной дистрибутивной решетки.
Copyright c by the paper’s authors. Copying permitted for private and academic purposes.
In: A.A. Makhnev, S.F. Pravdin (eds.): Proceedings of the 47th International Youth School-conference “Modern Problems in
Mathematics and its Applications”, Yekaterinburg, Russia, 02-Feb-2016, published at http://ceur-ws.org
Что можно сказать о сложности задачи Check-Id(A), если исходная конечная алгебра A обладает
меньшими, чем булевы алгебры, ¾выразительными возможностями¿, например, если A полугруппа, группа,
кольцо, решетка? Этот вопрос также явно ставился в [
Имеется большой массив работ, посвященных задаче проверки тождеств в кольцах, группах и
полугруппах. (Заметим, что в некоторых из этих работ задача проверки тождеств фигурирует под названием
¾задача эквивалентности термов¿.) Мы не будем здесь давать обзор таких работ, а отметим только
несколько результатов, важных с точки зрения вопросов, рассматриваемых в данной заметке. Во-первых, в классе
полугрупп известны примеры [
В данной заметке рассматривается задача проверки тождеств в конечных решетках. Единственной работой на эту тему, которую нам удалось обнаружить, является статья [2]. Из ее результатов вытекает, что задача CHECK-ID(L) является co-NP-полной для любой неодноэлементной дистрибутивной решетки L. По-видимому, под влиянием этого факта у исследователей сложилось впечатление, что для случая решеток проблематика, связанная со сложностью проверки тождеств, исчерпана. Однако полугрупповые примеры, упомянутые в предыдущем абзаце, указывают на некоторую преждевременность такого заключения: хотя каждая неодноэлементная решетка содержит неодноэлементную дистрибутивную решетку в качестве подрешетки, это не исключает существование конечных решеток с полиномиальной задачей проверки тождеств. Мы не знаем, существуют ли такие примеры.
Другое направление, которое подсказано обсуждавшимися выше результатами о задаче проверки тождеств в кольцах, состоит в рассмотрении тождеств определенного вида. Будем по аналогии с кольцевым случаем называть решеточные операции сложением и умножением и обозначать их соответственно знаком + и отсутствием точки. Наш основной результат показывает, что существует полиномиальный алгоритм, который проверяет в любой фиксированной неодноэлементной конечной решетке справедливость тождества p = q, в котором оба терма p и q представлены в виде суммы одночленов. С другой стороны, мы выводим из конструкции, использованной в [2], что для неодноэлементной дистрибутивной решетки задача проверки тождеств, у которых только одна из частей приведена к сумме одночленов, остается co-NP-полной. 2
Основные результаты Теорема. Пусть (L = L; +; ) неодноэлементная конечная решетка. Существует полиномиальный алгоритм, который проверяет, выполнено ли в L тождество p = q при условии, что оба терма p и q представлены в виде суммы одночленов.
Доказательство. Упомянутый полиномиальный алгоритм основан на следующем наблюдении. Лемма. Тождество (x1 _ x2 _ x3) ^ (:x1 _ x2) ^ (:x2 _ x3) ^ (:x2 _ :x3); (2) Левая часть этого тождества по построению есть сумма одночленов. В [2] показано, что тождество (2) не выполняется в неодноэлементной дистрибутивной решетке тогда и только тогда, когда исходная формула F (x1; : : : ; xn) выполнима. Для удобства читателя воспроизведем аргумент из [2] в немного упрощенном виде (в [2] рассматриваются не решетки, а алгебры гораздо более общего вида, что делает доказательство более громоздким).
Допустим, что формула F (x1; : : : ; xn) выполнима, и пусть ' : fx1; : : : ; xng ! f0; 1g выполняющий набор значений истинности переменных, т.е. F ('(x1); : : : ; '(xn)) = 1. Рассмотрим множество f0; 1g как двухэлементную решетку, в которой 0 + 1 = 1 и 0 1 = 0. Проинтерпретируем в этой решетке переменные x1; : : : ; xn в соответствии со значением функции ', а каждой переменной yi, i = 1; : : : ; n, придадим значение 1 '(xi). Тогда произведение (x1 + y1) : : : (xn + yn), а вместе с ним и вся правая часть тождества (2) примет значение 1. Значение же многочлена f (x1; : : : ; xn; y1; : : : ; yn) совпадет со значением формулы :F (x1; : : : ; xn), т.е. будет равно 0. Мы видим, что тождество (2) не выполняется в решетке f0; 1g.
Обратно, допустим, что тождество (2) не выполняется в какой-то неодноэлементной дистрибутивной решетке. Поскольку все неодноэлементные дистрибутивные решетки удовлетворяют одним и тем же тождествам, (2) не выполнено и в решетке f0; 1g. Последнее возможно только, если при некоторой интерпретации переменных x1; : : : ; xn; y1; : : : ; yn в решетке f0; 1g значение многочлена f (x1; : : : ; xn; y1; : : : ; yn) есть 0, а значение многочлена (x1 + y1) (xn + yn) равно 1. Из последнего факта следует, что для каждого i = 1; : : : ; n хотя бы одна из переменных xi и yi принимает значение 1. Зафиксируем для каждого i = 1; : : : ; n одну такую переменную и затем заменим рассматриваемую интерпретацию на интерпретацию ', которая на выбранной переменной также дает 1, а на второй переменной с тем же индексом принимает значение 0. По построению '(xi) 6 (xi) и '(yi) 6 (yi) для каждого i = 1; : : : ; n, а поскольку решеточные многочлены монотонны, заключаем, что
f ('(x1); : : : ; '(xn); '(y1); : : : ; '(yn)) 6 f ( (x1); : : : ; (xn); (y1); : : : ; (yn)): Правая часть этого неравенства по выбору интерпретации равна 0, значит, и левая часть равна 0. Итак, интерпретация ' обращает в 0 многочлен f (x1; : : : ; xn; y1; : : : ; yn) и при этом по построению такова, что '(yi) = 1 '(xi) для каждого i = 1; : : : ; n. В силу последнего свойства ее можно рассматривать как интерпретацию булевых переменных x1; : : : ; xn, а в силу первого формула :F (x1; : : : ; xn) ложна при этой интерпретации. Поэтому ' : fx1; : : : ; xng ! f0; 1g будет выполняющим набором значений истинности переменных для формулы F (x1; : : : ; xn). Список литературы [1] M. Garey, D. Johnson. Computers and intractability: a guide to the theory of NP-completeness. N.Y.: W.H.
Freeman & co, 1979. [2] P. A. Bloniarz, H. B. Hunt III, D. J. Rosenkrantz. Algebraic structures with hard equivalence and minimization problems. J. ACM 31(4):879–904, 1984. [3] S. Burris, J. Lawrence. The equivalence problem for finite rings. J. Symbolic Computation, 15(1), 67–71, 1993. [4] S. Burris, H. P. Sankappanavar. A Course in Universal Algebra. Berlin: Springer-Verlag, 1981. [5] G. Horva´th. The complexity of the equivalence problem over finite rings. Glasgow Math. J., 54(1), 193–199, 2012. [10] S. Seif. The Perkins semigroup has co-NP-complete term-equivalence problem.
Computation, 15(2), 317–326, 2005.
Checking identities in finite lattices
Ural Federal University (Yekaterinburg, Russia)