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

Маркелов, Николай Константинович

О сложности функций κ-значной логики в классе поляризованных полиномов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Маркелов, Николай Константинович АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Москва МЕСТО ЗАЩИТЫ

2013 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

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

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

Московский государственный университет имени М.В. Ломоносова Факультет вычислительной математики и кибернетики

На правах рукописи

' е./ /

005051145

Маркелов Николай Константинович

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

01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

2 8 МАР 2013

Москва-2013

005051145

Работа выполнена на кафедре математической кибернетики факультета вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова.

Научный руководитель: кандидат физико-математических наук,

доцент Селезнева Светлана Николаевна

Официальные оппоненты: доктор физико-математических наук,

профессор Кочергин Вадим Васильевич

кандидат физико-математических наук Дайняк Александр Борисович

Ведущая организация: Московский энергетический институт

(Национальный исследовательский университет)

Защита диссертации состоится «/1|» апреля 2013 года в 11 часов на заседании совета Д 501.001.44 при факультете вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, 2-й учебный корпус, факультет ВМК, аудитория 685. Желающие присутствовать на заседании диссертационного совета должны сообщить об этом за два дня по тел. (495)939-30-10 (для оформления заявки на пропуск).

С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ имени М.В. Ломоносова. С текстом автореферата можно ознакомиться на официальном сайте ВМК МГУ http://cs.msu.ru в разделе «Наука» - «Работа диссертационных советов» — «Д 501.001.44».

Автореферат разослан «/2 » марта 2013 г.

Ученый секретарь

диссертационного совета профессор й^Г Трифонов Н.П.

Общая характеристика работы

Актуальность темы

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

Одним из стандартных способов задания функций fc—значной логики являются полиномы. Первые результаты по представлениям булевых функций в виде полиномов были опубликованы в 1928 и 1929 году в работах И.И.Жегалкина2,3. Эти исследования были связаны с решением проблемы арифметизации логических рассуждений и не получили распространения вне этой области.

Только с развитием теории кодирования в 50-е годы были продолжены исследования по полиномиальным представлениям булевых функций. В par ботах Д. Мюллера4 и И. Рида5 полиномы Жегалкина были переоткрыты и получено их обобщение для введения нового класса линейных кодов, получивших название «коды Рида-Мюллера», а введенные полиномиальные формы стали называться «формами Рида-Мюллера».

Появление интереса непосредственно к полиномиальным представлениям булевых функций как объектам исследования связано с практическими приложениями. Развитие электроники во второй половине двадцатого века в направлении увеличения быстродействия, уменьшения энергоемкости и стоимости привело к тому, что большая интеграция имеет определяющее значение. Лучшей считается схема, имеющая меньшую площадь кристалла. Этот критерий и технологические требования регулярности структуры привели к требованию отображать на кристалл функцию или систему функций в виде дизъюнктивной, конъюнктивной или полиномиальной нормальной формы — матричной схемы. Такие схемы получили название программируемых логических матриц (ПЛМ)6.

'Яблонский С. В. Функциональные построения в /с-значной логике // Труды математического института им. В. А. Стеклова АН СССР. Т. 51. 1958. С. 5-142.

аЖегалкин И. И. Арифметизация символической логики // Мат. сборник. 1928. Т.35. С. 311-373.

3Жегалкин И. И. Арифметизация символической логики // Мат. сборник. 1929. Т.36. С. 305-338.

4Muller D. Е. Application of Boolean algebra to switching circuit design and to error detection // IRE Trans. Electron. Comput. EC-3. 1954. P. 6-12.

5 Reed I. S. A class of multiple-error-correcting codes and the decoding scheme // IRE Trans,

on Inform. Theory. 1954. P. 38-49.

вУгрюмов E. П. Цифровая схемотехника. СПб, БХВ-Петербург, 2004.

Более того, в последние годы полиномиальные представления булевых и к—значных функций находят и другие применения, например, в задачах машинного обучения7'8, кодирования и защиты информации.9 Они широко используются в теории сложности при нахождении нижних оценок сложности схем10'11. Полиномиальные представления также применяются в комбинаторно-графовых задачах12.

При простых к любая функция к—значной логики представима полиномом по модулю к13. При составных к существуют не полиномиальные функции. Кроме того, полиномиальные формы можно понимать в различных обобщенных смыслах. Исследуются различные поляризованные (понятие поляризации вводится по-разному) полиномиальные формы14'15, полиномы над кольцом целых чисел16, обощенные полиномы17, квазиполиномы18, кронекеровы матричные формы19.

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

'Klivans A. Servedio R. Learning DNF in time 2<5("1/3) // in Proceedings of the 33rd Annual Symposium on Theory of Computing (STOC'Ol). 2001. P. 258-265.

'Jackson J., Klivans A., Servedio R. Learnability beyond AC 0 // in Proceedings of the 34th ACM Symposium on Theory of Computing. 2002. P. 77&-784.

»MacWilliams F., Sloan N. The Theory of Error-Correcting Codes. North-Holland, 1977. 762 p.

"Aspnes J., Beigel R., Furst M., Rudich S. The expressive power of voting polynomials // Combinatorica, vol. 14, no. 2. 1994. P. 135-148.

"Разборов А. А. Нижние оценки размера схем ограниченной глубины в полном базисе, содержащем функцию логического сложения // Матем. заметки, ДАН СССР 41:4, 1987. С. 598-607.

"Gopalan P. Constructing Ramsey graphs from Boolean function representations //In Proceedings of the 21 st IEEE Conference on Computational Complexity (CCC'06). 2006. P. 115-128.

"Яблонский С. В. Функциональные построения в к—значной логике // Труды математического института им. В. А. Стеклова АН СССР. Т. 51. 1958. С. 5-142.

"Селезнева С. Н. О сложности представления функций многозначных логик поляризованными полиномами // Дискретная математика том 14, выпуск 2. 2002. С. 48—53.

"Селезнева С. Н. О сложности поляризованных полиномов функций многозначных логик, зависящих от одной переменной // Дискретная математика том 16, выпуск 2. 2004. С. 117-120.

16GopalanP., Shpilka A., Lovett S. The Complexity of Boolean Functions in Different Characteristics // Computational Complexity vol. 19, no. 2. 2010. P. 235-263.

"Селезнева C.H., Дайняк А.Б. О сложности обобщенных полиномов к—значных функций // Вестник Моск. Унив. Серия 15. Вычисл. матем. и кибернетика. 2008. С. 34-39.

"Селезнева С. Н. О сложности k-значных функций в одном классе полиномов // Проблемы теоретической кибернетики. Материалы XVI международной конференции. Нижний Новгород: Издательство Нижегородского госуниверситета, 2011. С. 430-434.

19Балюк А. С., Добрынина Ю. А. Нижняя оценка сложности k-значных функций в классе кронекеровых матричных форм Синтаксис и семантика логических систем // Материалы 4-й Российской школы-семинара, посвященной 80-летию основания Бурятского государственного университета. Улан-Удэ, 2012. С. 20-22.

классе схем из функциональных элементов к настоящему времени найдены только линейные нижние оценки сложности индивидуальных функций, в то время как мощностным методом доказано20'21, что почти все функции являются «сложными». Модель поляризованных полиномов является одной из моделей, для которой удается строить нелинейные нижние оценки сложности индивидуальных функций. Для булевой логики Н. А. Перязевым были построены индивидуальные последовательности «сложных» в классе поляризованных полиномов функций. При к ^ 3 для к—значной логики вопрос построения последовательностей сложных функций пока остается открытым.

В диссертации рассматриваются поляризованные полиномиальные формы функций /с—значной логики при простых к.

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

Сложностью функции к—значной логики в классе поляризованных полиномов называется минимальное по всем поляризациям число слагаемых с ненулевыми коэффициентами поляризованного полинома, реализующего эту функцию. Функция Шеннона от п определяется как сложность самой сложной функции от п переменных.

Для булевой логики первые оценки функции Шеннона были опубликованы Т. Sasao и Р. Beselich22, потом они были улучшены В. П. Супруном23. Точное значение функции Шеннона в классе полиномиальных поляризованных форм было найдено Н. А. Перязевым24. Для случаев А;—значной логики при к > 3 известные к настоящему времени верхняя25 и нижняя26 оценки функции Шеннона совпадают лишь по порядку роста.

Цель работы

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

20Shannon С.Е. The synthesis of two-terminal switching circuits. // Bell Syst. Techn, vol. 28, no. 1. 1949. P. 59-98.

"Лупанов О. В. Об одном подходе к синтезу управляющих систем — принципе локального кодирования // Проблемы кибернетики. Вып. 14 М.: Наука, 1965. С. 31-110.

»Sasao Т., Besslich P. On the complexity of mod-2 sum PLA's // IEEE Trans, on Comput, vol. 39, no. 2. 1990. P. 262-26

"В. П. Супрун, Сложность булевых функций в классе канонических поляризованных полиномов // Дискретная математика, том 5, выпуск 2. 1993. С. 111—115.

"Перязев Н. А. Сложность булевых функций в классе полиномиальных поляризованных форм // Алгебра и логика, т. 34, вып. 3. 1995. С. 323-326.

«Алексеев В.В., Вороненко A.A., Селезнева С.Н. О сложности реализации функций к-значной логики поляризованными полиномами // Труды V Международной конференции «Дискретные модели в теории управляющих систем». М.: МАКС Пресс, 2003. С. 8-9.

Методы исследования

При исследовании функции Шеннона сложности функций в классе поляризованных полиномов оказались полезны последовательности периодических функций. Функция называется периодической с периодом р, если вектор ее значений представляет собой многократно повторяющийся вектор р. Последовательностью периодических функций называется последовательность функций {/¡} от г переменных с одинаковыми периодами. Сложность последовательности периодических функций определяется как функция от количества переменных пив каждой точке равна сложности соответствующей периодической функции. Последовательности периодических функций, сложность которых есть о малое от функции Шеннона, будем называть вырожденными. Последовательности функций, не являющиеся вырожденными, назовем невырожденными.

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

Научная новизна

Все результаты диссертации ялвяются новыми. Основные результаты диссертации состоят в следующем (при простых к).

• Разработан быстрый алгоритм преобразования вектора значений функции к—значной логики в вектор коэффициентов ее поляризованного полинома.

• Для трехзначной логики улучшена нижняя оценка функции Шеннона в классе поляризованных полиномов и представлены периодические функции, на которых эта оценка достигается.

• Для пятизначной логики доказана вырожденность всех последовательностей периодических функций с периодами длины 6 и невырожденность всех последовательностей периодических функций с периодами длины 7 и суммой компонент периода равной нулю.

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

• Получена нижняя оценка сложности последовательностей невырожденных функций А;—значной логики в классе поляризованных полиномов.

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

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

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

Практическая значимость

Диссертация носит теоретический характер.

Интерес к исследованию сложности функций в классе поляризованных полиномов объясняется тем, что в настоящее время при проектировании цифровых устройств применяются программируемые логические матрицы (ПЛМ) типа РЬХСЖС. Основой для проектирования устройств на базе ПЛМ такого типа являются канонические поляризованные полиномы реализуемых булевых функций. Известные оценки функции Шеннона в классе поляризованных полиномов устанавливают необходимое и достаточное число промежуточных шин ПЛМ для реализации произвольных булевых функций от п переменных.

Апробация работы

Основные результаты были представлены автором на следующих конференциях:

• XV международная конференция «Проблемы теоретической , кибернетики» (Казань, 2-7 июня 2008 г.)

• VIII Международная научная конференция «Дискретные модели в теории управляющих систем» (Москва, 6-9 апреля 2009 г.)

• X Международный семинар «Дискретная математика и ее приложения» (Москва, 1-6 февраля 2010 г.)

• XVI международная конференция «Проблемы теоретической кибернетики» (Нижний Новгород, 20-25 июня 2011 г.)

• XI Международный семинар «Дискретная математика и ее приложения» (Москва, 18-23 июня 2012 г.)

• Научная конференция «Тихоновские чтения» (Москва, 29 октября - 2 ноября 2012 г.)

Публикации

Основные результаты диссертации опубликовано в семи работах [1-7], в том числе работы [2,5] в изданиях из Перечня ВАК.

Структура и объем диссертации

Диссертация состоит из пяти глав, двух приложений и списка литературы. Объем диссертации 81 станица. Список литературы содержит 58 наименований.

Содержание работы

В первой главе описана история вопроса, основные результаты и структура диссертации.

Во второй главе вводятся основные понятия. И представлены известные оценки функции Шеннона в классе поляризованных полиномов.

Пусть к ^ 2-, Ек = {0,1,. • •, к - 1}. Функция f(xn) называется функцией k—зшчной логики, если на всяком наборе а е Eg ее значение содержится в Ек. Совокупность всех функций fc-значной логики от п переменных обозначается через Р£. Для функции fc-значной логики f(x0,xi,...,x„-i) ее i-й остаточной функцией (i € Ек) по переменной х0 будем называть функцию fi(xux2,Xn-i) = f(i, xux2l..., xn-i). Каждую функцию fc—значной логики можно задавать вектором ее значений ак" = {а0, сц,..., at»-i), где координата а; — это значение функции на наборе, представляющем запись числа i в к—ичной системе счисления.

Полиномом назовем такую сумму (все суммы и произведения берутся по mod к)

£ Cf(a)-x%>.....С-/,

а=(оо.....a„_i)e£IJ

в котором с$(а) € Ек — некоторые коэффициенты.

Поляризованным по вектору поляризации а — (его,■■■,°Vi-i) € Щ полиномом назовем сумму (все суммы и произведения берутся по mod к)

сЦа) ■ (х0 + стоТ0.....(xn-i + ^n-i)0-1.

a=(a0,...,a„_i)e££

в котором сЦа) £ Ек — некоторые коэффициенты, и (xj + <п)"' — степени, то есть

(х{ + спТ = 1 • (а?< + • {xi + <п).....(xt + .

<ч раз

Назовем вектором коэффициентов поляризованного по вектору поляризации а € Щ полинома функции f(xn) € Р£ вектор значений функции <ff(xn).

Сложностью 1{Р°) полинома, поляризованного по вектору ст, назовем число слагаемых с ненулевыми коэффициентами. Сложность функции /с-значной логики / в классе поляризованных полиномов определяется как минимальная

по всем векторам поляризации а € сложность полинома Р", реализующего функцию /.

Функция Шеннона Ьк(п) определяется как сложность самой сложной функции к—значной логики от п переменных в классе поляризованных полиномов.

Точное значение функции Шеннона для булевой логики в 1995 году было найдено Н. А. Перязевым27:

■2п+Г

Ь2(п) -

где [■] обозначает целую часть.

Для функций к—значной логики верхняя оценка функции Шеннона была получена С. Н. Селезневой в 2002 году28:

^Щ^тт*"-

В 2003 году нижняя мощностная оценка функции Шеннона была опубликована В. Б. Алексеевым, А. А. Вороненко и С. Н. Селезневой29:

Ьк(п) >

Точное значение функции Шеннона от единицы было в 2004 году найдено С. Н. Селезневой30

Ьк(1) = к-1

Для трехзначной логики в 2006 году в дипломной работе Е. Н. Денисова31 экспериментально было установлено, что при п ^ 10 имеет место оценка

Г3„

Lz{n) >

43"

"Селезнева С. Н. О сложности представления функций многозначных логик поляризованными полиномами // Дискретная математика том 14, выпуск 2. 2002. С. 48-53.

"Алексеев В. В., Вороненко А. А., Селезнева С. Н. О сложности реализации функций к-значной логики поляризованными полиномами // Труды V Международной конференции «Дискретные модели в теории управляющих систем». М.: МАКС Пресс, 2003. С. 8-9.

"Денисов E.H. О сложности функций трехзначной логики в классе поляризованных полиномов. Дипломная работа, кафедра математической кибернетики, ВМиК МГУ им. Ломоносова, 2006

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

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

Над векторами из 1и векторами поляризации из Eg определим (индукцией по п) следующее преобразование Wk-

а) Если п = 1 и а = (ао, ai, ■ ■ ■, a(k~i)) £ Е% и а = /То в Ек, то

к-1 к-1 к-i Wh{&, а) = (<Х-аа, • • •. -X^J-^' ~ Л

у=0 i=0 j=0

при этом под компонентами с отрицательными индексами q_¿ подразумеваются компоненты ak-i-

б) Предположим, что операция Wk уже определена для каждого вектора из Eif и вектора поляризации а' = (oí, о"2, • • -, crn) € Eg и рассмотрим произвольный вектор

а = (а0)ai,..., a(fc»+i_i)) = (á°, a1,...,a*-1), где a* E E¡¡г € E* и вектор поляризации а = (<т0, ai,..., ап) € Е£+1. Пусть

Wk{a°,cS) =

Wk(a\a') = (А},/?},... = . . . ,

V) = А*-1,..., /3¡z}) = 0*-1

известны по индуктивному предположению. Положим

fc-l k-1 i-l

Wk(o, a) = - £/"^'"Л • • ■. - - E^"170)-

j=0 j=o j=o

где сумма наборов подразумевается как покомпонентная.

Тогда справедлива следующая

ТЕОРЕМА 3.2.1

Пусть к - простое число. Вектор a¡ значений функции f{xn) £ Р* сея-зсш с вектором pj коэффициентов поляризованного по вектору а полинома Р(хп), реализующего функцию f{xn) следующим образом: р/ = Wk(af,a).

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

В четвертой главе, разделенной на девять параграфов, проводится исследование сложности периодических функций.

Через (ao,ai,... ах-i)k" обозначим вектор длины кп вида

ao,aii---QT_i,ao,ail...aT_i, •■• ao,ai,...aT-i,ao,ai,...am,

где т = (к" mod Т) - 1

Функцию к—значной логики f(xo,..., xn-i) будем называть периодической с периодом р = (ро> • • • ,Pt-i)i если вектор ее значений имеет вид

а/ = (po,...,pT-i)k"•

Последовательностью периодических с периодом р Е Е^ функций будем называть последовательность

{/п} = fi{xi),f2(zi,x2), fn(x i, х2,хп),.......,

составленную из периодических функций с одинаковым периодом р от различного количества переменных, равного индексу функции в последовательности. Для последовательности периодических функций {/„} определим ее сложность в классе поляризованных полиномов Lynj(n) = L(fn).

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

ТЕОРЕМА 4.1.11

Периодические булевы функции с периодами (110), (101), (011) является самыми сложными булевыми функциями в классе поляризованных полиномов.

Во втором параграфе для трехзначной логики улучшена ранее известная нижняя оценка функции Шеннона и предъявлены последовательности периодических функций, на которых эта оценка достигается.

ТЕОРЕМА 4.2.9

Сложность периодических функций трехзначной с периодами (1122), (1221), (2211), (2112) в классе поляризованных полиномов равна

|3" — если п — нечетно, и

|3" + если п — четно.

ТЕОРЕМА 4.2.10

Справедлива следующая нижняя оценка функции Шеннона сложности функций трехзначной логики в классе поляризованных полиномов:

Ь3(п) >

[М

В третьем параграфе вводится преобразование ft, многократное применение которого в некотором смысле моделирует преобразование Wk вектора значений функций fc-значной логики в вектор коэффициентов поляризованного полинома применительно к периодическим функциям. Пусть р е Для каждого i € Ek вводится преобразование

%,т ■ Етк Eh

Отображение Щт(р) содержательно выдает первые к компонент циклического сдвига вектора р на ik позиций влево. Формально

Ф*,г(р) = (Pj>P(j+l) mod Г, • • • >P{j+k-l) mod т) >

где j = ik mod Т.

Обозначим через : Е% х Ек (Е{)к следующее отображение

ft£ (р,а) =

= (№(ф°(р)^)[О], .... w^-^^m), . . . ,

(Wk(V°(p),<7)lk - 1],..., Wk(VT-1(P),°)[k ~ I]))-

При этом векторы

ПтМЮ = №(Ф°(р),а)М,...)Щ(Фг-1(р),а)[г])

назовем О,—образами вектора р.

Матрицу преобразования ftr(p,a)[i] будем обозначать через А?. В четвертом параграфе доказаны критерии невырожденности индивидуальных последовательностей функций &-значной логики и невырожденности целых семейств последовательностей периодических функций, сводящие вопросы о невырожденности к вычислительным задачам. А также доказана нетривиальная нижняя оценка сложности периодических функций в классе поляризованных полиномов.

ТЕОРЕМА 4.4.3

Пусть к — простое число. Если Т взаимно просто с к, то период р € Е]: является вырожденным тогда и только тогда, когда найдется натуральное тп и такие параметры ¿1, ¿2, •• •, гт, ¿1,5?,..., 5т, что выполнено

где (0,0,..., 0) — нулевой вектор.

ТЕОРЕМА 4.4.5

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

ТЕОРЕМА 4.4.6

Пусть к — простое число. Если Т взаимно просто с к, то для того, чтобы все периоды длины Т с нулевой суммой компонент были невырождены необходимо и достаточно, чтобы для любых г, а € у однородных систем линейных уравнений с матрицами А° не было решений помимо (сс...с), где (сс...с) — вектор, все компоненты которого равны с.

ТЕОРЕМА 4.4.7

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

ТЕОРЕМА 4.4.4

Пусть к — простое число. Если Т взаимно просто с к, а последовательность периодических функций {/п} с периодом длины Т невырождена, то ее сложность

кп

к/М = шп) ^

В пятом параграфе в общем виде рассматривается матрица преобразоваг ния П и делается несколько замечаний о ее свойствах.

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

ТЕОРЕМА 4.6.5

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

ТЕОРЕМА 4.7.12

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

В восьмом параграфе и, подробнее, в приложении В описаны экспериментальные результаты, подкрепляющие гипотезу о том, что все последовательности периодических функций к—значной логики (при к ^ 3) с периодами длины Т > к + 1 и нулевой суммой периода компонент являются невырожденными.

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

ТЕОРЕхМА 4.9.1

Пусть к иТ — простые числа, причем Т > кк~1. Тогда все периоды длины Т с нулевой суммой компонент являются невырожденными. При этом последовательность функций {/„} с периодом Т имеет сложность

кп

£{/„)(") = Шп) > 2Т2АГ

В пятой главе перечислены основные результаты диссертации, выносимые на защиту.

Публикации автора по теме диссертации

[1] Маркелов Н. К. Селезнева С. Н. Быстрый алгоритм построения векторов коэффициентов поляризованных полиномов к—значных функций // Тезисы докладов XV Международной конференции «Проблемы теоретической кибернетики». Казань: Отечество, 2008. С. 102.

[2] Селезнева С. Н., Маркелов Н. К. Быстрый алгоритм построения векторов коэффициентов поляризованных полиномов значных функций // Ученые записки Казанского университета Сер. Физико-математические науки, Т. 151, вып. 2. 2009. С. 147-153.

[3] Маркелов Н. К. О сложности некоторых к-значных функций в классе поляризованных полиномов // Материалы X Международного семинара «Дискретная математика и ее приложения» (Москва, 1-6 февраля 2010 г.). М.: Издательство механико-математического факультета МГУ. С. 191-193.

[4] Маркелов Н. К. О сложности периодических функций трехзначной логики в классе поляризованных полиномов // Материалы XVI Международной конференции (Нижний Новгород, 20-25 июня 2011 г). Изд-во Нижегородского госуниверситета, 2011. С. 301-303.

[5] Маркелов Н. К. Нижняя оценка сложности функций трехзначной логики в классе поляризованных полиномов // Вестник Московского университета. Сер. 15, Вычислительная математика и кибернетика. 2012. №3. С. 40-45.

[6] Маркелов Н. К. Критерий невырожденности периодических функций

значной логики // Материалы X Международного семинара «Дискретная математика и ее приложения»(Москва, 18-23 июня 2012 г). С. 199-202.

[7] Маркелов Н. К. О сложности в классе поляризованных полиномов периодических функций значной логики с периодами большой длины // Научная конференция «Тихоновские чтения», тезисы докладов (Москва, 29-31 октября 2012 г). М.: МАКС Пресс, 2012. С. 50.

Напечатано с готового оригинал-макета

Подписано в печать 05.03.2013 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 080 экз. Заказ 057.

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к. Тел. 8(495)939-3890/91. Тел./факс 8(495)939-3891.

Текст научной работы диссертации и автореферата по математике, кандидата физико-математических наук, Маркелов, Николай Константинович, Москва

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ

М. В. ЛОМОНОСОВА

На правах рукописи

04201355400

МАРКЕЛОВ НИКОЛАЙ КОНСТАНТИНОВИЧ

О СЛОЖНОСТИ ФУНКЦИЙ /с-ЗНАЧНОЙ ЛОГИКИ В КЛАССЕ ПОЛЯРИЗОВАННЫХ ПОЛИНОМОВ

ДИССЕРТАЦИЯ

на соискание ученой степени кандидата физико-математических наук по специальности 01.01.09 "Дискретная математика и математическая кибернетика"

Научный руководитель: к. ф.-м. н., доцент С. Н. Селезнева

МОСКВА - 2013

Содержание

1 Введение

2 Основные понятия 8

3 Алгоритмы построения векторов коэффициентов полиномов 10

3.1 Алгоритм построения вектора коэффициентов полинома по вектору функции в &-значной логике .................10

3.2 Алгоритм построения вектора коэффициентов поляризованного полинома по вектору функции в /г-значной логике......18

3.3 Экспериментальные результаты к главе 3.............22

4 Исследование периодических функций 23

4.1 Булевы функции в классе поляризованных полиномов......23

4.2 Исследование функций трехзначной логики периода длины 4 . . 27

4.3 Преобразование в применении к периодическим функциям . 37

4.4 Общие утверждения о сложности периодических функций ... 45

4.5 О структуре матриц .......................51

4.6 Исследование функций пятизначной логики с периодами длины 6 54

4.7 Исследование функций пятизначной логики с периодами длины 7 57

4.8 Экспериментальные результаты к главе 4.............70

4.9 О сложности периодических функций к—значной логики большого периода.............................70

5 Заключение 72 А Сложные функции от малого числа переменных 73

В Ранг матриц 75

1 Введение

Одним из стандартных способов задания функций к—значной логики являются полиномы. Первые результаты по представлениям булевых функций в виде полиномов были опубликованы в 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]. Для случаев к—значной логики при к^З известные к настоящему времени верхняя [27] и нижняя [1] оценки функции Шеннона совпадают лишь по порядку роста. Интерес к исследованию сложности функций в классе поляризованных полиномов объяс-

няется тем, что в настоящее время при проектировании цифровых устройств применяются программируемые логические матрицы (ПЛМ) типа РЬХСЖС. Основой для'проектирования устройств на базе ПЛМ такого типа являются канонические поляризованные полиномы реализуемых булевых функций. Известные оценки функции Шеннона в классе поляризованных полиномов устанавливают необходимое и достаточное число промежуточных шин ПЛМ для реализации произвольных булевых функций от п переменных.

При исследовании функции Шеннона сложности функций в классе поляризованных полиномов оказались полезны последовательности периодических функций. Функция называется периодической с периодом р, если вектор ее значений представляет собой многократно повторяющийся вектор р. Последовательностью периодических функций называется последовательность функций {/¿} от I переменных с одинаковыми периодами. Сложность последовательности периодических функций определяется как функция от количества переменных пив каждой точке равна сложности соответствующей периодической функции. Последовательности периодических функций, сложность которых есть о малое от функции Шеннона, будем называть вырожденными. Последовательности функций, не являющиеся вырожденными, назовем невырожденными.

В настоящей работе получены следующие результаты:

• Представлен быстрый алгоритм преобразования вектора значений функции к—значной логики в вектор коэффициентов ее поляризованного полинома.

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

• Для пятизначной логики доказана вырожденность и невырожденность некоторых последовательностей периодических функций.

• Для к—значной логики найден критерий невырожденности последовательностей периодических функций, сводящий вопрос о невырожденности конкретных функций к вычислительной задаче полиномиальной по

значности логики к и экспоненциальный по длине периода Т.

• Получена нижняя оценка сложности последовательностей невырожденных функций к—значной логики в классе поляризованных полиномов.

• Для к—значной логики найден критерий невырожденности семейств последовательностей периодических функций, сводящий вопрос о невырожденности семейств функций к вычислительной задаче полиномиальной по значности логики к и длине периода Т. <

• Для А;—значной логики показано, что периодические функции с достаточно большой длиной периода являются невырожденными в классе поляризованных полиномов.

Основные результаты диссертации опубликованы в [17-22,25] и были представлены автором на следующих конференциях:

• XV международная конференция «Проблемы теоретической кибернетики» (Казань, 2-7 июня 2008 г.)

• X Международный семинар «Дискретная математика и ее приложения» (Москва, 1-6 февраля 2010 г.) ,

• XVI международная конференция «Проблемы теоретической кибернетики» (Нижний Новгород, 20-25 июня 2011 г.)

• XI Международный семинар «Дискретная математика и ее приложения» (Москва, 18-23 июня 2012 г.)

• Научная конференция «Тихоновские чтения» (Москва, 29 октября - 2 ноября 2012 г.)

Диссертация состоит из пяти глав, двух приложений и списка литературы. В первой главе описана история вопроса, основные результаты и структура диссертации.

Во второй главе вводятся основные понятия.

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

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

В третьем параграфе вводится преобразование моделирующее итерацию преобразования вектора значений функций А;—значной логики в вектор коэффициентов поляризованного полинома применительно к периодическим функциям.

В четвертом параграфе доказаны критерии невырожденности индивидуальных последовательностей функций к—значной логики и невырожденности целых семейств последовательностей периодических функций. А также доказана нетривиальная нижняя оценка сложности периодических функций в классе поляризованных полиномов.

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

В шестом и седьмом параграфах на невырожденность исследуются периодические функции пятизначной логики с периодами длин 6 и 7.

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

В пятой главе вкратце приводятся основные результаты диссертации, выносимые на защиту.

2 Основные понятия

Пусть к ^ 2, Ek = {0,1,..., к — 1}. Функция f(xn) называется функцией к—значной логики, если на всяком наборе а £ ЕЦ ее значение содержится в Ek. Совокупность всех функций к—значной логики от п переменных обозначается через PJ}. Для функции к—значной логики /(жо>х\,...,хп-\) ее г—й остаточной функцией (г £ Ek) по переменной xq будем называть функцию /г(жь Х2, ■ ■ ■, xn-i) — /(г, Х\,Х2, •.., £n_i). Каждую функцию А;—значной логики можно задавать вектором ее значений ак" = (о;о5 скъ ..., &кп-i)> где координата аг — это значение функции на наборе, представляющем запись числа i в к—ичной системе счисления.

Полиномом назовем такую сумму (все суммы и произведения берутся по mod к)

Е с/(й) • хо.....

а=(а0,...,ап_1)еЯ£

в котором df(a) £ Ek — некоторые коэффициенты.

Поляризованным по вектору поляризации а = (оо,... ,crn-i) £ полиномом назовем сумму (все суммы и произведения берутся по mod к)

Е caf(a) ■ {х0 + <70)ао.....(жп-1 +

а=(а0,...!ап-1)€Е£

в котором cj(a) £ Ek — некоторые коэффициенты, и (хг + аг)а1 — степени, то есть

(хг + аг)а' = 1 • (хг + аг) ■ (хг + аг).....(хг + аг).

а, раз

Ясно, что, если а = (0,..., 0), то поляризованный по вектору а полином -обычный полином по mod к.

Под записью Ра будем понимать полином, поляризованный по вектору а. Каждая функция f(xn) £ PJ} однозначно задается полиномом по модулю к [33]. В [27] показано, что для каждого вектора поляризации а £ Е

каждая функция f(xn) G PJ} пред ставима поляризованным по вектору а полиномом единственным образом. Далее в работе будем везде считать, что к — простое число. Под к всюду далее будет пониматься значность логики.

Назовем вектором коэффициентов поляризованного по вектору поляризации er G Е^ полинома функции f(xn) G Р£ вектор значений функции с^(хп).

Обозначим за К вектор всевозможных элементарных произведений п переменных, в котором они упорядочены лексикографически, то есть для j G Е%п верно Kj = x%qX%i ... где выражение ¿o^i... in — запись числа j в к—ичной системе счисления.

Тогда / =< р,К >, если р — вектор коэффициентов полинома функции /, а < • , • > — скалярное произведение векторов.

Сложностью 1(Ра) полинома, поляризованного по вектору а, назовем число слагаемых с ненулевыми коэффициентами. Сложность функции А;-значной логики / в классе поляризованных полиномов определяется как минимальная по всем векторам поляризации а G Eß сложность полинома Ра, реализующего функцию /.

LH) = min l(Pa).

Функция Шеннона Lfc(n) определяется как сложность самой сложной функции к—значной логики от п переменных в классе поляризованных полиномов.

Первая нижняя оценка функции Шеннона для булевой логики была получена в 1990 году Т. Sasao и Р. Beselich [57]:

I/2 (n) ^ 2 • 2п/2 - 2, для четных п.

В 1993 году В. П. Супруном была получена верхняя и улучшена нижняя оценка функции Шеннона [31]:

1/2(п) < 3 • 2П-2, для п ^ 2;

/ п

Ып) > г /91 V [п/щ,

Точное значение функции Шеннона для булевой логики в 1995 году было найдено Н. А. Перязевым'[23]:

"оп+Г

Ь2(п) =

где [•] обозначает целую часть.

Для функций к—значной логики верхняя оценка функции Шеннона была получена С. Н. Селезневой в 2002 году [27]:

к(к -1) + Г •

В 2003 году нижняя мощностная оценка функции Шеннона была опубликована В. Б. Алексеевым, А. А. Вороненко и С. Н. Селезневой [1]:

Ьк(п) >

Точное значение функции Шеннона от единицы было в 2004 году найдено С. Н. Селезневой [28]

Ьк(1) = к-1

Для трехзначной логики в 2006 году в дипломной работе Е. Н. Денисова [11] экспериментально было установлено, что при п ^ 10 имеет место оценка

Ьз{п) ^

^ОП

3 Алгоритмы построения векторов коэффициентов полиномов

Эта часть работы посвящена построению алгоритма преобразования векторов значений функций /с-значной логики в векторы коэффициентов их поляризованных полиномов.

Подобные алгоритмы в булевом случае для неполяризованных полиномов можно найти в [10], а для поляризованных — в [30], а также в таких зарубежных работах, как [41,45].

Случай к-значной логики для неполяризованных полиномов был исследован Ю. В. Таранниковым (не опубликовано).

3.1 Алгоритм построения вектора коэффициентов полинома по вектору функции в /с-значной логике

Докажем две вспомогательные леммы. (Ранее они доказывались, например, в [15]). Будем иметь в виду, что в формулировках и доказательствах все арифметические операции производятся по модулю к.

Лемма 3.1.1. [15] Для каждого простого к верно, что

у> Г"1' Р = к-1 ^ \ 0,

Доказательство.

Рассмотрим сначала случай р = к — 1. Тогда по малой теореме Ферма

к-1

г=1

В случае 1 ^ р ^ к — 2 доказательство проведём по индукции. Базис индукции (р — 1).

г=1

в силу чётности числа к — 1. Индуктивный переход. . Допустим, что лемма верна для всех 1 ^ р ^ т — 1 ^ А; — 3, и проверим справедливость для р = т:

/с—1

о = кт+1 = ((г + 1)ш+1 - гт+1) =

г=0

= Е ((т + ^ + Ш(т2+1)*т-1 • ■ • + (т + 1)г + 1) .

Тогда, пользуясь предположением индукции, получаем к-1 / , ы

г=0 г=0

+ {т-1)т(т+1)!£.т_2