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

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

Содержание
1 Введение
2 Основные понятия
3 Алгоритмы построения векторов коэффициентов полиномов
3.1 Алгоритм построения вектора коэффициентов полинома по вектору функции в /с-значной логике
3.2 Алгоритм построения вектора коэффициентов поляризованного полинома по вектору функции в Аьзначной логике
3.3 Экспериментальные результаты к главе
4 Исследование периодических функций
4.1 Булевы функции в классе поляризованных полиномов
4.2 Исследование функций трехзначной логики периода длины
4.3 Преобразование в применении к периодическим функциям
4.4 Общие утверждения о сложности периодических функций
4.5 О структуре матриц А°
4.6 Исследование функций пятизначной логики с периодами длины
4.7 Исследование функций пятизначной логики с периодами длины
4.8 Экспериментальные результаты к главе
4.9 О сложности периодических функций к—значной логики большого периода
5 Заключение
А Сложные функции от малого числа переменных
В Ранг матриц А°

1 Введение
Одной из основных составляющих дискретных моделей являются функции к—значной логики. Они начали изучаться в 50-е годы прошлого века в связи с развитием вычислительной техники. Фундаментальными вопросами в данной области являются вопросы полноты, выразимости, канонических форм и другие [34].
Одним из стандартных способов задания функций А;—значной логики являются полиномы. Первые результаты по представлениям булевых функций в виде полиномов были опубликованы в 1928 году в работах И.И.Жегалкина [12, 13]. Эти исследования были связаны с решением проблемы арифметизации логических рассуждений и не получили распространения вне этой области.
Только с развитием теории кодирования в 50-е годы были продолжены исследования по полиномиальным представлениям булевых функций. В работах Д. Мюллера [52] и И. Рида [53] полиномы Жегалкина были переоткры-ты и получено их обобщение для введения нового класса линейных кодов, получивших название «коды Рида-Мюллера», а введенные полиномиальные формы стали называться «формами Рида-Мюллера».
Появление интереса непосредственно к полиномиальным представлениям булевых функций как объектам исследования связано с практическими приложениями. Развитие электроники во второй половине двадцатого века в направлении увеличения быстродействия, уменьшения энергоемкости и стоимости привело к тому, что большая интеграция имеет определяющее значение. Лучшей считается схема, имеющая меньшую площадь кристалла. Этот критерий плюс технологические требования регулярности структуры привели к требованию отображать на кристалл функцию или систему функций в виде дизъюнктивной, конъюнктивной или полиномиальной нормальной формы — матричной схемы. Такие схемы получили название программируемых логических матриц (ПЛМ) [2,3,7,8,56-58].
Более того, в последние годы полиномиальные представления булевых и к—значных функций находят и другие применения, например, в задачах машинного обучения, кодирования и защиты информации [44,46-51]. Они широко используются в теории сложности при нахождении нижних оценок сложности схем [24,35-37,55]. Полиномиальные представления также применяются в комбинаторно-графовых задачах [38,42,43].

При простых к любая функция к—значной логики представима полиномом по модулю к [34]. При составных к существуют не полиномиальные фунцции. Кроме того, полиномиальные формы можно понимать в различных обобщенных смыслах. Исследуются различные поляризованные (понятие поляризации вводится по-разному) полиномиальные формы [4,5,27,28], полиномы над кольцом целых чисел [39], обощенные полиномы [14,26,40], квазиполиномы [29], кронекеровы матричные формы [6].
В теории управляющих систем важной задачей является получение нижних (и точных) оценок сложности для конкретных функций. Например, в классе схем из функциональных элементов к настоящему времени найдены только линейные нижние оценки сложности индивидуальных функций, в то время как мощностным методом доказано, что почти все функции являются «сложными» [16,54]. Модель поляризованных полиномов является одной из моделей, для которой удается строить нелинейные нижние оценки сложности индивидуальных функций. Для булевой логики Н. А. Перязевым были построены индивидуальные последовательности «сложных» в классе поляризованных полиномов функций. При к 3 для А;—значной логики вопрос построения последовательностей сложных функций пока остается открытым.
В диссертации рассматриваются поляризованные полиномиальные формы функций А;—значной логики при простых к.
Поляризованный полином это сумма с некоторыми коэффициентами произведений переменных, встречающихся всюду с фиксированным количеством отрицаний Поста.
Сложностью функции А;—значной логики в классе поляризованных полиномов называется минимальное по всем поляризациям число слагаемых с ненулевыми коэффициентами поляризованного полинома, реализующего эту функцию. Функция Шеннона от п определяется как сложность самой сложной функции от п переменных.
• Для булевой логики первые оценки функции Шеннона были опубликованы Т. Завао и Р. ВеввисЬ в [57], потом которые были улучшены В. П. Супруном в [31]. Точное значение функции Шеннона в классе полиномиальных поляризованных форм было найдено Н. А. Перязевым в [23]. Для случаев А;—значной логики при к 3 известные к настоящему времени верхняя [27] и нижняя [1] оценки функции Шеннона совпадают лишь по порядку роста. Интерес к исследованию сложности функций в классе поляризованных полиномов объяе-

Предположим, что на г-м шаге разложения (0 г < п— 1) имеется а слагаемых типа 1 и 6 слагаемых типа 0. Тогда на следующем шаге при сг„_г+г = 1 получим За слагаемых типа 1 и 36 слагаемых типа 0. Если же стп_г+1 ф 1, то получим 2а + 6 слагаемых типа 1 и 26 + а слагаемых типа 0. Таким образом, вне зависимости от поляризации, имеем число слагаемых типа 1 больше, чем число слагаемых типа 0. а
Лемма 4.2.7. Для сложностей Ь(фп),Ь(~/п),Ь(дп),Ь(—дп),Ь(ип), В(—ип),Ь(ип),Ь(—уп) имеет место одно из следующих утверждений:
1) В финальной сумме число слагаемых Ь{ф) совпадает с числом слагаемых Ь(д), а число слагаемых Ь{щ) отличается от числа слагаемых Ь(у) ровно на единицу;
2)В финальной сумме число слагаемых Ь(ф) отличается от числа слагаемых Ь(дф) ровно на единицу, а число слагаемых Ь(щ) совпадает с числом слагаемых Ь(у).
Доказательство. Доказательство проведем индукцией по шагам разложения.
Если сделано 0 шагов разложения, то утверждение леммы верно в силу того, что слагаемое всего одно.
Докажем индуктивный переход, рассмотрев два случая.
1. Пусть на каком-то шаге гг — г,г = 1,,п — 1, получено равное число слагаемых Ь{уф и Ь(щ), а слагаемых Т(/г) (Ь(дф) на 1 больше, чем слагаемых
ЬШ (МИ)-
Тогда на следующем шаге, если ср — 1, соотношение числа слагаемых типа 0 не изменится, как и соотношение числа слагаемых типа 1.
Если же огф 1, то соотношение числа слагаемых типа 1 станет равным, а слагаемых Ь{щ) станет на 1 меньше (больше) при а,- = 0 и больше (меньше) при о = 2, чем слагаемых Т(гД.
2. Пусть на каком-то шаге имеется равное число слагаемых Т(Д) и Ь(дф, а слагаемых Т(гД (Ь(щ)) на 1 больше, чем слагаемых типа Ь(щ) (Ь(иф). Тогда на следующей итерации при а = 1 соотношение числа слагаемых типа 1 не изменится, а соотношение числа слагаемых типа 0 изменится на противоположное.
Если же а Ф 1, то соотношение числа слагаемых Ь(дф станет на 1 меньше (больше) при сг = 0 и больше (меньше) при сг = 1, чем слагаемых типа Т(Д),