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

В настоящей работе исследуются свойства многочленов над конечными полями, зависящих от многих аргументов, и вопрос об алгоритмической сложности распознавания свойств функций к-значной логики, представленных полиномами. В частности, рассматривается проблема распознавания полноты.

Проблема распознавания полноты систем функций многозначной логики, как и более общая проблема выразимости, является одной из важных проблем дискретной математики и берет свое начало в большом исследовании Э. Поста, опубликованном в 1921 году [4]. Это исследование касалось алгебры логики и полностью решало проблему построения всех замкнутых систем алгебры логики. В частности, в нем содержался критерий полноты произвольной системы функций алгебры логики. Формулировка его такова: система функций алгебры логики неполна тогда и только тогда, когда она содержится в одном из пяти известных замкнутых классов, а именно классов монотонных, линейных, самодвойственных функций и функций, сохраняющих константы. Таким образом, из этого критерия следует, что проблема выявления полноты системы функций сводится к проблемам распознавания некоторых свойств отдельно взятой функции.

Позже, в 1941 году, указанное исследование вышло в виде монографии [25], в которой ставился вопрос об обобщении полученных результатов на случай функций многозначной логики.

Критерий полноты для функций многозначной логики был получен в 1957 году А. В. Кузнецовым [8]. Он опирается на понятие предпол-ного класса, введенное в работах С. В. Яблонского и А. В. Кузнецова, и формулируется следующим образом: система функций к-значной логики неполна тогда и только тогда, когда она содержится в одном из конечного числа предполных классов.

Таким образом, аналогично случаю булевых функций проблема выяснения полноты системы функций сводится к распознаванию принадлежности функции предполным классам. Доказательство критерия полноты Кузнецова не содержало конструктивного описания всех предполных классов. Поэтому усилия многих математиков в 19 571 965 годах были направлены на описание всех предполных классов. Отдельные их типы были описаны в работах [9, 10, 11]. Окончательный результат был получен И. Розенбергом [12, 14].

С развитием вычислительной техники возник вопрос о рассмотрении проблемы полноты систем функций с алгоритмической точки зрения. Здесь следует отметить несколько аспектов.

Функция — суть абстрактный объект. И при решении теоретических вопросов, вообще говоря, не важно, как функция представлена. Однако алгоритмическая процедура имеет дело с данными. Поэтому рассмотрение функций как входных данных для алгоритмических процедур предполагает реализацию функций определенным образом. Мы говорим, что для представления функций /с-значной логики выбирается некоторый язык в самом общем смысле. Язык, по меньшей мере, должен обладать тем свойством, что каждая функция может быть записана в нем. Примерами языка могут служить векторы значений функций, формулы над определенным базисным множеством формул и т. д. Очевидно, что язык, в котором функции реализованы, существенно определяет алгоритм распознавания свойств функций. Другими словами, априори зная, как функция представлена, каковы свойства такого ее представлении, мы пытаемся максимально использовать эти знания при построении алгоритма распознавания свойств функций.

Важной характеристикой алгоритмической процедуры является ее сложность, которая, напомним, есть функция длины входных данных. Представления одной и той же функции в различных языках имеют различную длину. И поэтому сложность распознавания свойств функции также зависит от способа задания функции. С другой стороны, понятие алгоритмической процедуры можно формализовывать по-разному. И, вообще говоря, сложность будет зависеть и от выбранной формальной алгоритмической модели. Напомним, что в зависимости от алгоритмической сложности решения задачи делятся на классы, среди которых выделены классы полиномиально решаемых и NР-полных [31]. И для двух различных стандартных формальных алгоритмических моделей из принадлежности задачи какому-то из этих классов в одной из них следует принадлежность этому же классу в другой. Поэтому если ограничиваться исследованием вопроса о принадлежности задачи одному из этих классов, то выбор формальной алгоритмической модели не имеет значения.

Вопрос об алгоритмической сложности распознавания принадлежности реализованных векторами значений функций &—значной логики предполным классам исследовался в работах В. Б. Алексеева и П. Р. Емельянова [15,16,17, 23]. При таком представлении функций к-значной логики непосредственно из определения предполных классов следует полиномиальная решаемость поставленной задачи. Поэтому в указанных работах строятся алгоритмы распознавания, имеющие меньшую сложность, чем алгоритмы, основанные на определениях предполных классов. Если же функции реализуются формулами в общем случае, то задача оказывается N Р-поткж. Возникает вопрос, будет ли иметь задача полиномиальное решение, если на вид формул будут наложены дополнительные ограничения. Одним из примеров таких формул функций двузначной логики являются дизъюнктивные и конъюнктивные нормальные формы. Известно, что если функции заданы в виде дизъюнктивных (конъюнктивных) нормальных форм, то задача выяснения полноты системы функций остается ]УР-полной.

Другим примером формул с ограничениями служат полиномы. Полином может рассматриваться как формула особого вида над базисным множеством формул, представляющих собой некоторые функции й-значной логики, называемые сложением, умножением и константой 1.

Алгебраическая структура, в которой каждое отображение может быть записано полиномом, называется полиномиально полной. Исследования относительно полиномиально полных алгебраических структур можно найти в [3, 7, 13, 27]. В них было доказано, что среди ненулевых колец полиномиально полными являются только конечные поля. В [32], со ссылкой на алгебраические результаты, было показано, что каждая функция к-значной логики может быть представлена полиномом тогда и только тогда, когда к = рн, где р — простое число, И > 1. В этом случае на множестве Е— {0,1,., к — 1}, на котором определены аргументы функций &—значной логики, можно ввести двуместные операции, относительно которых Е^ образует поле. И рассматриваемые полиномы будут таковыми относительно этих операций поля Е^.

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

В первой части работы рассматриваются многочлены над конечными полями, зависящие от нескольких переменных. Исследуется вопрос о нахождении необходимых условий того, что в многочлене содержится довольно большое число слагаемых. Получено одно из таких условий — инвариантность многочлена. Многочлен называется инвариантным, если он, будучи рассмотрен как отображение, не изменяется при замещении каждой его переменной некоторыми многочленами одного аргумента. Следует отметить, что в доказываемых свойствах многочленов существенной является зависимость от нескольких переменных (аналогичные свойства для многочленов одного аргумента очевидны). Известны различные целочисленные характеристики многочленов, например, степень и т. д.. Мы рассматриваем целочисленные характеристики многочленов от нескольких переменных. Это ранг и вес. Эти характеристики приобретают смысл только для многочленов многих переменных (для многочленов одного аргумента они вырождаются в совпадающие). Доказываемое небходимое свойство инвариантных многочленов представляет собой неравенство между их рангом и весом (теорема 1.1). Этим неравенством утверждается, что число слагаемых инвариантных многочленов не меньше значений определенной экспоненциальной функции от их ранга.

Во второй части работы исследуется вопрос об алгоритмической сложности распознавания свойств функций /с-значной логики, представленных полиномами. Рассматривается проблема распознавания полноты, которая, как указано выше, сводится к конечному числу проблем распознавания принадлежности функции к-значной логики предполным классам. Доказана полиномиальная решаемость задачи о распознавании полноты функций двузначной логики, представленных полиномами (теоремы 2.1, 2.2 и 2.3). При к > 3 доказана полиномиальная решаемость задач о принадлежности функции к-значной логики, представленной полиномом, предполным классам самодвойственных, монотонных функций, функций, сохраняющих разбиение, и предполным классам типа В (теоремы 2.4, 2.5, 2.6 и следствия из них). При построении требуемых алгоритмов применяются свойства многочленов над конечными полями, полученные в первой части, а также другие свойства функций к-значной логики, доказываемые в соответствующих разделах.

Результаты, представленные в работе, опубликованы в научных журналах [20, 22], а также докладывались на XI и XII Международных конференциях «Проблемы теоретической кибернетики» (Ульяновск, июнь 1996 года и Нижний Новгород, май 1999 года соответственно), II и III Международных конференциях «Дискретные модели в теории управляющих систем» (Красновидово, июнь 1997 и 1998 годов соответственно), тезисы докладов опубликованы [18, 19, 21, 24].

Часть I. Некоторые свойства многочленов над конечными нолями, зависящих от нескольких переменных.