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

• Автор: Бухман, Антон Владимирович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 83 с.

Оглавление
Введение
Основные определения
1. Распознавание свойств булевых функций
1. Распознавание инвариантности относительно преобразования Мёбиуса
2. Распознавание чётности функции
3. Связь чётности и инвариантности относительно преобразования Мёбиуса
4. Распознавание периодичности
2. Сохранение предикатов функциями многозначной логики
1. Некоторые одноместные центральные предикаты
2. Применение обобщённых полиномов к задаче распознавания сохранения функцией предикатов
3. Неполиномиальные алгоритмы
1. Проверка принадлежности функций, заданных полиномами, одному классу Поста
2. О распознавании сохранения некоторых двухместных центральных предикатов функциями из Рз
3. Об одном алгоритме распознавания сохранения множества полиномом малого ранга
Заключение
Приложение
Литература

Введение
Дискретные функции являются одним из основных объектов исследовании в математике [28]. Интерес к ним вызван тем, что они имеют ряд приложений на практике. Например, дискретные функции используются в синтезе СБИС [29], кодировании [22], анализе программ [16], криптографии [21] и других прикладных областях.
Среди дискретных функций можно выделить класс булевых функций. Эти функции возникли из логики [36, 37]. Для них можно рассмотреть операцию суперпозиции. Множество булевых функций с введённой па нем операцией образует алгебру - так называемую булеву алгебру (или алгебру логики) [30]. При таком подходе основными вопросами теоретических исследований становятся проблемы полноты, выразимости и представления. Первые результаты для булевых функций как алгебраических объектов были получены Э. Постом (Б. Post) в [39, 40]. В этих работах Постом были описаны все замкнутые классы булевых функций, в частности, был получен критерий полноты системы функций. Этот критерий утверждает, что система полна тогда и только тогда, когда целиком не лежит ни в одном из конечного числа предполных классов.
После изучения Постом булевых функций, возник вопрос об исследовании их естественного обобщения - функций многозначных логик. Среди ранних работ по этой тематике молено отмстить [18, 28, 33] и другие. С.В. Яблонским [28] были описаны все предполные классы функций трёхзначной логики. А.И. Кузнецов [18] получил критерий полноты для функций многозначных логик, который утверждал, что существует конечное число предполных классов. Некоторые предполные классы были описаны в работах [28, 23, 41]. И окончательное описание всех предполных классов в /с-зпачпой логике дал Розенберг [42, 43].
Отметим, что все перечисленные результаты являются теоретическими в том смысле, что булевы функции рассматриваются как абстрактный объект и не приводятся никакие эффективные методы проверки принадлежности функций тем или иным классам (кроме работы [18]). Поэтому, для того чтобы на практике использовать результаты из [28, 42, 43], надо построить эффек-

тивпые алгоритмы проверки критериев Кузнецова, Поста и др. И для этих алгоритмов надо выбрать некоторый способ представления функций.
Любая функция конечпозпачпой логики имеет конечную область определения. Поэтому каждую такую функцию можно задать, явно выписав значения на всех аргументах. Чтобы определить функцию /с-зиачной логики от п переменных нужно определить её значения на кп аргументах. Это можно сделать, выписав вектор значений функции, который будет содержать кп элементов. Это очень простой способ задания. Он подходит для функций от небольшого числа переменных. На практике встречаются функции зависящие от 100 и более аргументов. Поэтому задание функции в виде вектора значений не всегда может быть реализовано. Важными, особенно с практической точки зрения, становятся другие способы представления функций консчнозпачных логик. Среди них можно отметить формулы, СФЭ, ДНФ, КНФ, совершенные ДНФ и КНФ, алгебраические нормальные формы, полиномиальные формы [30, 21, 24, 15].
Остановимся более подробно па полиномиальном способе задания функций. Полипом по модулю к - это сумма попарно различных мономов, причём сложение и умножение рассматриваются по модулю к. Известно [30], что каждая Аьзначпая функция задаётся полиномом по модулю к тогда и только тогда, когда к - простое число. Вообще, существуют такие функции от п переменных, полиномы которых содержат кп слагаемых. Но па практике встречаются функции, которые могут быть заданы короткими полиномами. Поэтому в ряде случаев полиномиальное представление является достаточно эффективным. Полиномы являются ещё и алгебраическими объектами, поэтому, работая с ними, можно использовать алгебраический аппарат [20]. Кроме того, полиномы являются нормальными формами. А нормальные формы (дизъюнктивные, конъюнктивные, полиномиальные) являются основой для построения некоторых цифровых преобразователей информации, например, программируемых логических матриц (ПЛМ) [2, 6].
На практике встречаются задачи, для которых требуется использовать дискретные функции, обладающие определёнными свойствами. Под свойством мы будем понимать предикат (эффективно вычислимый), который действует на множестве функций /с-значной логики. Будем считать, что функция

Объединяя вместе (15) и (16) получаем К'к{т) < I.

Следствие 6. Пусть / - периодическая функция, т - её период, и моном К £ 11/. Тогда длина полинома К(х + г) не превосходит I2.
Доказательство.
Пусть К' слагаемое полинома П/ такое, что К' € К(х + г). Каждому такому слагаемому можно поставить в соответствие множество К!к,{т). Эти множества будут попарно не пересекаться и в объединении дадут всё множество слагаемых полинома К(х + т). В каждом множестве, в силу следствия 1, не более I слагаемых, и всего множеств не более /. Получаем, что число слагаемых полинома К(х + т) не превосходит I2.

Возможность построения полиномиального алгоритма для задачи проверки является ли заданный вектор т периодом функции, заданной полиномом, вытекает из следствия 6.
Утверждение 5. Существует детерминированный алгоритм, который, получив на вход запись полинома булевой функции / 6 Р2 и набора т из пулей и единиц, определяет за полиномиальное время, является ли набор г периодом /.
Доказательство.
Алгоритм будет следующим:
У1. Проверяем, что для каждого слагаемого К полинома П/ будет верно, что полином К(х + т) содержит количество слагаемых меньше либо равно 12, где I - длина полинома П/. Если хотя бы для одного слагаемого это условие нарушается, то согласно следствию 6, т не может быть периодом функции. Алгоритм завершает свою работу и выдаёт ответ “НЕТ”.
У2. Вычисляем полином П/^+т). Для этого сначала для каждого слагаемого К € П/ находим полином К(х + т). Мы получим полипом с не более, чем /3 слагаемыми. В полученном полиноме приведём подобные слагаемые. Данное действие займёт 0(№) шагов алгоритма. Сравним полученный полином с исходным. Если они совпадают, то т является периодом функции, иначе - нет.