=Paper=
{{Paper
|id=Vol-1662/alg1
|storemode=property
|title=Задача проверки тождеств в конечных решетках(Checking identities in finite lattices)
|pdfUrl=https://ceur-ws.org/Vol-1662/alg1.pdf
|volume=Vol-1662
|authors=Ekaterina V. Bogomolova,Nikita V. Kitov
}}
==Задача проверки тождеств в конечных решетках(Checking identities in finite lattices)==
https://ceur-ws.org/Vol-1662/alg1.pdf
Задача проверки тождеств в конечных решетках
Е. В. Богомолова Н. В. Китов
cyberkiller@mail.ru
УрФУ (Екатеринбург)
Аннотация
Исследуется сложность задачи проверки тождеств в конечных ре-
шетках. Показано, что тождества, обе части которых представлены
в виде суммы одночленов, можно проверить за время, полиноми-
альное от размера тождества, в любой конечной решетке, а задача
проверки тождеств, у которых в виде суммы одночленов представ-
лена только одна часть, является co-NP-полной для любой неодно-
элементной дистрибутивной решетки.
1 Постановка задачи
Мы предполагаем, что читатель знаком с исходными понятиями универсальной алгебры и сложности
вычислений в объеме начальных глав учебников [4, 1, 9], и будем свободно ими пользоваться.
Пусть A — произвольная, но фиксированная конечная алгебра. Задача проверки тождеств в алгебре
A, обозначаемая CHECK-ID(A), — это комбинаторная задача распознавания, входными данными которой
служат всевозможные пары (p, q) термов в сигнатуре алгебры A, а ответами — «ДА» или «НЕТ» в зави-
симости от того, выполнено или не выполнено тождество p = q в этой алгебре. Эта задача алгоритмически
разрешима — если термы p и q в совокупности зависят от m переменных, то можно поочередно подставлять
вместо переменных всевозможные m-ки элементов алгебры A и проверять, приводят ли такие подстанов-
ки к равным значениям термов p и q. Очевидно, что время работы такого прямолинейного алгоритма в
худшем случае экспоненциально зависит от размера входных данных, так как число m-ок, подлежащих
перебору, равно |A|m . С другой стороны, для любой конечной алгебры A задача CHECK-ID(A) принад-
лежит классу сложности co-NP: если для какой-то пары термов (p, q) тождество p = q не выполняется
в алгебре A, то недетерминированный полиномиальный алгоритм может угадать m-ку элементов из A,
опровергающую данное тождество, и подтвердить свою догадку, вычислив значения термов p и q на этой
m-ке, что требует лишь полиномиального от размера термов p и q числа шагов типа «Подсчитать резуль-
тат операции над известными элементами алгебры A». Поскольку алгебра A фиксирована и не является
частью входа, каждый такой шаг выполняется за константное время, и общее время работы алгоритма
ограничено многочленом от размера входа.
Исследовать вычислительную сложность задачи CHECK-ID(A) предложил М. В. Сапир в хорошо из-
вестном обзоре [7], см. там проблему 2.4. Как подмечено в [7, с. 402], если A – двухэлементная булева ал-
гебра, то задача Check-Id(A) равносильна «отрицанию» классической задачи Выполнимость. Поскольку
последняя NP-полна (см. [1, 9]), отсюда следует, что задача проверки тождеств в двухэлементной булевой
алгебре будет 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
1
Что можно сказать о сложности задачи Check-Id(A), если исходная конечная алгебра A обладает мень-
шими, чем булевы алгебры, «выразительными возможностями», например, если A — полугруппа, группа,
кольцо, решетка? Этот вопрос также явно ставился в [7].
Имеется большой массив работ, посвященных задаче проверки тождеств в кольцах, группах и полу-
группах. (Заметим, что в некоторых из этих работ задача проверки тождеств фигурирует под названием
«задача эквивалентности термов».) Мы не будем здесь давать обзор таких работ, а отметим только несколь-
ко результатов, важных с точки зрения вопросов, рассматриваемых в данной заметке. Во-первых, в классе
полугрупп известны примеры [8, 10], которые демонстрируют, что свойство конечной алгебры иметь по-
линомиально разрешимую задачу проверки тождеств, вообще говоря, не переносится на ее подалгебры
и гомоморфные образы. Соответственно, из того, что у некоторой алгебры A имеется подалгебра или
гомоморфный образ с co-NP-полной задачей проверки тождеств, вообще говоря, не следует, что и сама
алгебра A такова. Во-вторых, при изучении сложности задачи проверки тождеств в ассоциативных коль-
цах, выяснилось, что ситуация может существенным образом зависеть от формы записи тождеств. Ясно,
что каждое кольцевое тождество можно записать в виде f (x1 , . . . , xn ) = 0, где f (x1 , . . . , xn ) — многочлен
с целыми коэффициентами от некоммутирующих переменных x1 , . . . , xn . Если не накладывать никаких
априорных ограничений на вид многочлена f (x1 , . . . , xn ), то задача Check-Id(R) для конечного ассоци-
ативного кольца R разрешима за полиномиальное время, если кольцо R нильпотентно, и co-NP-полна,
если R ненильпотентно [6, 3]. Понятно, что любой многочлен можно записать в стандартной форме —
как сумму одночленов. Оказывается, задача проверки тождеств, левые части которых записаны в виде
суммы одночленов, разрешима за полиномиальное время, например, для любого конечного ассоциативно-
коммутативного кольца (это следует из работы [5], где получен даже несколько более общий результат).
Причина такого контраста на самом деле довольно проста: в теории сложности вычислений время работы
алгоритма для решения задачи измеряется функцией от длины входа этой задачи. В случае задачи про-
верки тождеств в кольце длиной входа является длина записи многочлена, и при переходе к стандартной
записи эта длина может экспоненциально вырасти. Например, в записи многочлена (x1 + y1 ) . . . (xn + yn )
используется 5n символов (если считать, что умножение, как обычно, обозначается отсутствием точки), а
если раскрыть все скобки и записать этот же многочлен в виде суммы одночленов, то таких одночленов
будет 2n и общая длина записи составит (n + 1)2n − 1. Поэтому алгоритм, работающий полиномиальное
время от длины стандартной записи, может оказаться экспоненциальным, если измерять время его работы
как функцию длины исходной записи.
В данной заметке рассматривается задача проверки тождеств в конечных решетках. Единственной ра-
ботой на эту тему, которую нам удалось обнаружить, является статья [2]. Из ее результатов вытекает,
что задача CHECK-ID(L) является co-NP-полной для любой неодноэлементной дистрибутивной решет-
ки L. По-видимому, под влиянием этого факта у исследователей сложилось впечатление, что для случая
решеток проблематика, связанная со сложностью проверки тождеств, исчерпана. Однако полугрупповые
примеры, упомянутые в предыдущем абзаце, указывают на некоторую преждевременность такого заклю-
чения: хотя каждая неодноэлементная решетка содержит неодноэлементную дистрибутивную решетку в
качестве подрешетки, это не исключает существование конечных решеток с полиномиальной задачей про-
верки тождеств. Мы не знаем, существуют ли такие примеры.
Другое направление, которое подсказано обсуждавшимися выше результатами о задаче проверки тож-
деств в кольцах, состоит в рассмотрении тождеств определенного вида. Будем по аналогии с кольцевым
случаем называть решеточные операции сложением и умножением и обозначать их соответственно знаком
+ и отсутствием точки. Наш основной результат показывает, что существует полиномиальный алгоритм,
который проверяет в любой фиксированной неодноэлементной конечной решетке справедливость тож-
дества p = q, в котором оба терма p и q представлены в виде суммы одночленов. С другой стороны,
мы выводим из конструкции, использованной в [2], что для неодноэлементной дистрибутивной решетки
задача проверки тождеств, у которых только одна из частей приведена к сумме одночленов, остается
co-NP-полной.
2 Основные результаты
Теорема. Пусть (L = L, +, ·) — неодноэлементная конечная решетка. Существует полиномиальный
алгоритм, который проверяет, выполнено ли в L тождество p = q при условии, что оба терма p и q
представлены в виде суммы одночленов.
Доказательство. Упомянутый полиномиальный алгоритм основан на следующем наблюдении.
2
Лемма. Тождество
u1 + u2 + · · · + uk = v1 + v2 + · · · + v` , (1)
где все ui и vj — одночлены (т.е. произведения переменных), выполнено в неодноэлементной решетке
(L = L, +, ·) тогда и только тогда, когда выполнены два условия
(i) для любого i ∈ {1, . . . , k} найдется такое j ∈ {1, . . . , `}, что каждая переменная из vj появляется в ui ;
(ii) для любого s ∈ {1, . . . , `} найдется такое t ∈ {1, . . . , k}, что каждая переменная из ut появляется в vs .
Доказательство леммы. Пусть u = u1 + u2 + · · · + uk , v = v1 + v2 + · · · + v` .
Необходимость каждого из условий (i) и (ii) доказывается методом контрапозиции. Предположим, на-
пример, что условие (i) нарушено. Тогда существует такое i ∈ {1, . . . , k}, что в каждом одночлене vj ,
j ∈ {1, . . . , `}, есть хотя бы одна переменная, которая не появляется в одночлене ui . Зафиксируем одну
такую переменную для каждого j ∈ {1, . . . , `} и обозначим ее через x[vj ]. (Переменные x[vj ], отвечающие
разным j, могут совпадать — важно только то, что каждая выбранная переменная входит в соответству-
ющий одночлен vj и что ни одна из них не входит в одночлен ui .) Поскольку решетка L неодноэлементна,
в ней найдутся такие различные элементы a, b, что ab = a, a + b = b. Рассмотрим интерпретацию перемен-
ных тождества (1) в решетке L, при которой все переменные x[vj ] принимают значение a, а все остальные
переменные принимают значение b. Тогда одночлен ui принимает значение b, а следовательно, такое же
значение принимает многочлен u. С другой стороны, значение каждого из одночленов vj будет равно a,
откуда и значение многочлена v равно a. Мы видим, что тождество (1) не выполняется в решетке L.
Аналогично рассуждаем в случае, когда нарушено условие (ii).
Для доказательства достаточности рассмотрим произвольный одночлен ui из u. Если условие (i) выпол-
нено, то в v найдется одночлен vj такой, что каждая переменная из vj появляется в ui . В силу коммутатив-
ности, ассоциативности и идемпотентности умножения отсюда следует, что либо ui = vj , либо ui = vj w для
некоторого одночлена w. Поэтому ui + vj = vj (в первом случае срабатывает идемпотентность сложения,
а во втором — закон поглощения). Используя ассоциативность и коммутативность сложения, получаем,
что ui + v = v, откуда u + v = v. Аналогично, из условия (ii) выводится, что u + v = u. Итак, u = v, т.е.
тождество (1) выполнено в решетке L. Лемма доказана.
Заключение теоремы сразу же следует из леммы, так как условия (i) и (ii) проверяются за линейное
время от размера тождества. Теорема доказана.
Замечание 1. Конечно, в отличие от обсуждавшегося во введении случая колец, не всякое тождество
произвольной решетки может быть переписано в виде равенства сумм одночленов. Это, однако, возможно
для тождеств дистрибутивной решетки. Как уже отмечалось, в [2] показано, что задача проверки в ко-
нечной неодноэлементной дистрибутивной решетке co-NP-полна. Хотя на первый взгляд этот результат
противоречит теореме, в действительности противоречия нет: как и в случае колец, разница в сложности
объясняется тем, что при приведении многочлена к сумме одночленов с помощью дистрибутивного закона
длина записи многочлена может экспоненциально возрастать.
Замечание 2. Назовем линейным многочлен, представляющий собой сумму переменных. Из двойствен-
ности между операциями сложения и умножения в решетках следует, что справедлив и двойственный
вариант теоремы: существует полиномиальный алгоритм, который проверяет, выполнено ли в данной ре-
шетке L тождество p = q при условии, что оба терма p и q представлены в виде произведений линейных
многочленов.
В заключение покажем, как из редукции, использованной в [2], вытекает, что для неодноэлементной
дистрибутивной решетки задача проверки тождеств, у которых одна из частей приведена к сумме од-
ночленов, остается co-NP-полной. Напомним, что входом задачи Выполнимость служит произвольная
булева формула F (x1 , . . . , xn ) в конъюнктивной нормальной форме, т.е. конъюнкция дизъюнкций пере-
менных и их отрицаний. Применяя законы де Моргана, запишем отрицание ¬F (x1 , . . . , xn ) этой формулы
в дизъюнктивной нормальной форме, т.е. в виде дизъюнкции конъюнкций переменных и их отрицаний.
Теперь преобразуем ¬F (x1 , . . . , xn ) в решеточный многочлен по следующему правилу: знак дизъюнкции
заменяем на знак +, знак конъюнкции — на отсутствие точки, а отрицание переменной xi — на новую пере-
менную yi . В результате получим многочлен f (x1 , . . . , xn , y1 , . . . , yn ), записанный в виде суммы одночленов.
Например, для случая, когда исходная формула F (x1 , . . . , xn ) есть
(x1 ∨ x2 ∨ x3 ) ∧ (¬x1 ∨ x2 ) ∧ (¬x2 ∨ x3 ) ∧ (¬x2 ∨ ¬x3 ),
3
дизъюнктивная нормальная форма ее отрицания есть
(¬x1 ∧ ¬x2 ∧ ¬x3 ) ∨ (x1 ∧ ¬x2 ) ∨ (x2 ∧ ¬x3 ) ∨ (x2 ∧ x3 ),
и описанное преобразование дает многочлен
y1 y2 y3 + x1 y2 + x2 y3 + x2 x3 .
Рассмотрим тождество
f (x1 , . . . , xn , y1 , . . . , yn ) = f (x1 , . . . , xn , y1 , . . . , yn ) + (x1 + y1 ) · · · (xn + yn ). (2)
Левая часть этого тождества по построению есть сумма одночленов. В [2] показано, что тождество (2) не
выполняется в неодноэлементной дистрибутивной решетке тогда и только тогда, когда исходная формула
F (x1 , . . . , xn ) выполнима. Для удобства читателя воспроизведем аргумент из [2] в немного упрощенном
виде (в [2] рассматриваются не решетки, а алгебры гораздо более общего вида, что делает доказательство
более громоздким).
Допустим, что формула F (x1 , . . . , xn ) выполнима, и пусть ϕ : {x1 , . . . , xn } → {0, 1} — выполняющий
набор значений истинности переменных, т.е. F (ϕ(x1 ), . . . , ϕ(xn )) = 1. Рассмотрим множество {0, 1} как
двухэлементную решетку, в которой 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) не выполняется в решетке {0, 1}.
Обратно, допустим, что тождество (2) не выполняется в какой-то неодноэлементной дистрибутивной
решетке. Поскольку все неодноэлементные дистрибутивные решетки удовлетворяют одним и тем же тож-
дествам, (2) не выполнено и в решетке {0, 1}. Последнее возможно только, если при некоторой интер-
претации ψ переменных x1 , . . . , xn , y1 , . . . , yn в решетке {0, 1} значение многочлена 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 ) ложна при
этой интерпретации. Поэтому ϕ : {x1 , . . . , xn } → {0, 1} будет выполняющим набором значений истинности
переменных для формулы 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. Horváth. The complexity of the equivalence problem over finite rings. Glasgow Math. J., 54(1), 193–199,
2012.
4
[6] H. B. Hunt III, R. E. Stearns. The complexity of equivalence for commutative rings. J. Symbolic Computation,
10(5), 411–436, 1990.
[7] O. G. Kharlampovich, M. V. Sapir. Algorithmic problems in varieties. Int. J. Algebra and Computation,
5(4-5), 379–602, 1995.
[8] O. Klı́ma. Complexity issues of checking identities in finite monoids. Semigroup Forum, 79(3), 435–444,
2009.
[9] C. H. Papadimitriou. Computational Complexity. Reading–Menlo Park–N.Y.: Addison-Wesley Publishing
Company, 1994.
[10] S. Seif. The Perkins semigroup has co-NP-complete term-equivalence problem. Int. J. Algebra and
Computation, 15(2), 317–326, 2005.
5
Checking identities in finite lattices
Ekaterina V. Bogomolova, Nikita V. Kitov
Ural Federal University (Yekaterinburg, Russia)
Keywords: lattice, lattice identity, co-NP-complete problem.
Abstract. We study the complexity of identity checking in finite lattices. We show that every identity whose
sides are both represented as sums of monomials can be checked in polynomial time in every finite lattice while
checking identities with only one side being a sum of monomials is co=NP-complete for every non-singleton
distributive lattice.
6