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

Бухман, Антон Владимирович

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

Бухман, Антон Владимирович АВТОР

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

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

2013 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

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

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

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

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

Бухман Антон Владимирович

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

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

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

1 О О КГ 7013 005534603

Москва - 2013

005534603

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

кандидат физико-математических наук, доцент Селезнева Светлана Николаевна.

доктор физико-математических наук, профессор Гашков Сергей Борисович; кандидат физико-математических наук, доцент Дайняк Александр Борисович.

Национальный исследовательский университет "МЭИ"

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

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

Автореферат разослан «¿¿» сентября 2013 г.

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

Ученый секретарь диссертационного совета к.т.н., ведущий научный сотрудник

Костенко В. А.

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

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

В диссертационной работе рассматриваются вопросы, связанные с распознаванием конкретных свойств функций булевой и многозначных логик. Основные результаты диссертации состоят в построении полиномиальных алгоритмов для проверки того, что функция (булева или многозначной логики), поданная на вход алгоритма в виде полинома, обладает некоторым, заранее известным свойством. Эта тематика актуальна с теоретической и практической точек зрения. Теоретический результат состоит в том, что доказана принадлежность классу Р ряда задач. На практике встречаются задачи, для которых требуется использовать дискретные функции, обладающие определёнными свойствами. Под свойством мы будем понимать предикат (эффективно вычислимый), который действует на множестве функций fc-значной логики. Будем считать, что функция обладает свойством, если предикат на ней истинен, иначе - она не обладает свойством.

1 Логачев О., Сальников А., Смышляев С., Ященко В. Булевы функции в теории кодирования и криптологии. 2-е изд., дополн. М.: МЦНМО, 2012.

2Ван Тилборг X. Основы криптологии. М.:Мир - 2006. - 471 с.

3Алексеев В.Б., Емельянов Н. Р. Метод построения быстрых алгоритмов в fc-значной логике, Матем.

заметки, 38:1, 1985. С. 148-156

■•Емельянов Н.Р. Об одном подходе к построению эффективных алгоритмов распознавания полноты

в многозначных логиках, Матем. заметки, 39:5, 1986. С. 766-775

5Voronenko A.A. On the complexity of the monotonicity verification. Proceedings of 15th Annual IEEE

Conference on Computational Complexity (July 4-7, 1999, Florence, Italy). P. 235-238.

вание свойств функций в случае, когда алгоритм получает на вход полином, был рассмотрен в работах С.П. Горшкова6, С.Н. Селезневой7,8'9, М.Н. Вялого10. В работах С.Н. Селезневой получены полиномиальные алгоритмы для проверки свойств, связанных с полнотой системы дискретных функций. В частности, был описан полиномиальный алгоритм для распознавания полноты системы булевых функций и построены полиномиальные алгоритмы для распознавания свойства сохранения функциями некоторых семейств предикатов, описанных в работах Розенберга11,12. Результаты С.П. Горшкова связаны с распознаванием свойства принадлежности булевых функций классам Шефера. В этой работе рассматривались различные способы задания функций, и в частности, полиномы. Были получены полиномиальные алгоритмы для проверки принадлежности булевых функций, заданных полиномами, всем классам Шефера.

Цель диссертационной работы.

Целью работы является построение быстрых алгоритмов для решения задач распознавания следующих свойств булевых функций: чётности, инвариантности относительно преобразования Мёбиуса и периодичности. А также построение быстрых алгоритмов распознавания сохранения fc-значными функциями некоторых центральных предикатов (при простых значениях к). Также в работе ставилась цель исследовать особенности полиномов функций,

8Горшков С.П. О сложности распознавания мультиаффинности, биюнктивности, слабой положительности и слабой отрицательности булевой функции. Обозрение прикл. и промышленной матем. Сер.

Дисхр.матем. 1997, 4, №2, С. 216-237.

'Селезнева С.Н. О сложности распознавания полноты множества булевых функций, реализованных

полиномами Жегалкина. Дискретная математика. 1997, 9:4. С. 24-31

? Селезнева С.Н. Полиномиальный алгоритм для распознавания принадлежности реализованной полиномом функции к-значной логики предполным классам самодвойственных функций. Дискретная математика. 1998, 10:3. С. 64-72.

'Селезнева С.Н. Полиномиальный алгоритм распознавания свойства функций многозначных логик, представленных полиномом, сохранять рефлексивный и транзитивный предикат. Тезисы докла, дов XII Международной конференции "Проблемы теоретической кибернетики "(Нижний Новгород, 1999).

М.:МГУ, 207.

10Вялый М.Н. Алгоритмические задачи с таблицами значений булевых полиномов. Труды ИСП РАН, Т.6, 2004. С. 51-64.

"Rosenberg I. La struct des fonctions de plusieurs variables sur un ensemble fini/ Comptes fendus? de

lÁcadem. Paris (1965) 260, 3817-3819.

"Rosenberg I. Über die funktionale Vollständigkeit in der mehrvertigen Logiken. Rozpravy Cescko-slovenskë

Académie vi Rada matematickych a pfirodnich véd. Praga, 1970, roînic 80, Seäit 4. P. 3-93.

обладающих перечисленными выше свойствами.

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

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

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

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

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

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

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

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

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

Основные результаты работы являются новыми и получены лично автором.

Практическая ценность.

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

Апробация.

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

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

• VIII молодёжная научная школа по дискретной математике и её приложениям (Москва, 24-29 октября 2011);

• Международный научно-практический семинар "Комбинаторные конфигурации и их приложения-2012" (Кировоград, 13-14 апреля 2012);

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

• Научная конференция "Тихоновские чтения 2012" (Москва, 29-31 октября 2012);

• XX Международная научная конференция студентов, аспирантов и молодых учёных "ЛОМОНОСОВ-2013" (Москва, 9-12 апреля 2013).

Публикации. По теме диссертации опубликовано 9 печатных работ, из них 2 в изданиях по перечню ВАК.

Объем и структура работы. Диссертация состоит из введения, трёх основных частей, заключения и приложения. Список использованной литературы содержит 56 наименований. Текст диссертации содержит 84 страницы машинописного текста.

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

В тексте диссертации используются следующие основные определения о обозначания.

Пусть к > 2 - натуральное число, Ек = {0к - 1}. Функцией к-значной логики, зависящей от п переменных, будем называть отображение вида / : Щ -> Ек- Множество всех функций к-значной логики будем обозначать посредством Рк■ Множество всех функций /с-значной логики, зависящих от п переменных будем обозначать через Р". Пусть /(хг,..., хп) е для краткости набор (а?1,...,х„) будем обозначать х и писать /(х). Также будем использовать обозначение /(£) для обозначения функции ¡(хи. . -,хп). На множестве можно ввести частичный порядок: для наборов (а\,..., ап) в

и (А, ■•■.&>) £ Щ будем писать {аи...,ап) < (/Зь... ,/?„), если аг < /?!,...,а„ < /Зп-

При к ~ 2 функции принято называть булевыми. Везде в дальнейшем умножение и сложение будем рассматривать по модулю к.

Мономом над переменными ..., х„ назовём любое выражение вида

^и----иг1>

где I > 1,1 < ¿ь..., ц < п, 1 < ... < к - 1, все переменные различны; либо просто 1. Равенство мономов рассматривается с точностью до перестановки сомножителей.

Полиномом назовём сумму по модулю к конечного числа различных мономов с ненулевыми коэффициентами из Ек или 0 (можно понимать как сумму нулевого числа мономов). Длиной полинома называется число его слагаемых. Длину нулевого полинома будем считать равной 0. Равенство полиномов рассматривается с точностью до перестановки слагаемых.

Любая &-значная функция задаёт полином по модулю к, причём однозначно тогда и только тогда, когда к - простое число. В данной работе будут рассматриваться /с-значные функции только при простых к. Так как в этом случае задание каждой функции полиномом однозначно, то через П/ будем обозначать полином функции /. В случае двухзначной логики полиномы по модулю 2 называют полиномами Жегалкина.

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

Далее рассмотрим вопрос о том, как полином подаётся на вход вычислителя. У многоленточной машины Тьюринга каждая лента, разбита на ячейки. Каждая ячейка может хранить к + 2 различных значений Л, 0,..., к - 1, ©.

Символ ® используется, чтобы отделять слагаемые полинома друг от друга. Символ А - пустой символ. Пусть на вход подаётся полином от п переменных, в котором I мономов. Опишем исходную конфигурацию. Будем считать, что в начальный момент времени на первой ленте машины справа от головки записано слово, соответствующее входному полиному. Это слово будет заполнять 1(п + 2) — 1 ячейку. Если мы пронумеруем ячейки слева направо начиная с О, то ячейки от (.?' - 1)(п + 2) до j(n + 2) - 1 относятся к ¿-ому слагаемому полинома, в том смысле, что в ячейке {] - 1)(п + 2) хранится коэффициент ¿-ого слагаемого полинома, а в ячейке (] - 1)(п + 2) + г хранится степень г-ой переменной ¿-ого слагаемого полинома. В ячейке с номером э{п + 2) - 1 хранится символ ©. Таким образом длина входа для полинома состоящего из I слагаемых и зависящего от п переменных равна N = 1(п + 2) -1. Остальные^ ленты машины Тьюринга пусты.

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

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

Пусть / е Р2П. Преобразованием Мёбиуса от функции / будем называть функцию д е такую, что для любого а £ Е% верно соотношение

0еЕ%ф<а

Преобразование Мёбиуса будем обозначать ¡1, и писать = д.

Булева функция / называется инвариантной относительно преобразования Мёбиуса, если для неё выполнено соотношение:

Основным результатом раздела является алгоритм 1, который проверяет по полиному булевой функции, поданному ему на вход, является ли функция, реализуемая этим полиномом, инвариантной относительно преобразования Мёбиуса.

Далее в теореме 2 даётся оценка сложности работы алгоритма 1 в худшем случае на двухленточной машине Тьюринга.

Теорема 2. Существует детерминированная двухленточная машина Тьюринга, которая по записи полинома булевой функции, поданному ей на вход, определяет, обладает ли эта функция свойством инвариантности относительно преобразования Мёбиуса, со сложностью 0(М3), где N — 1п, и I -длина полинома функции, ап - число её переменных.

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

В разделе 2 первой части исследуется вопрос об эффективном распознавании свойства чётности булевой функции, заданной в форме полинома.

Функция /(х) € Р2П называется чётной, если верно, что }(х) = /(£).

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

В диссертации описан алгоритм 2, который проверяет чётность булевой функции, поданной ему в виде полинома.

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

Теорема 4. Существует детерминированная двухленточная машина Тьюринга, которая по полиному булевой функции, поданному на её вход, определяет, обладает ли эта функция свойством чётности, со сложностью 0(Лг3), где N = 1п, и I - длина полинома функции, ап - число её переменных.

В разделе 3 первой части исследуется связь между функциями чётными и инвариантными относительно преобразования Мёбиуса. Вводится преобразование и, которое преобразует один полином в другой. Пусть П = К\ © ••• © - полином, который зависит от переменных х!,...,хп, положим

1/(П) = К[ © • • • © К[, где К- - это такие мономы, что гп^(К-) = {х\,..., хп} \ тй(К$, где тй{К) - множество переменных, которые входят в моном К.

Данное преобразоване обладает свойством описанным в теореме 5.

Теорема 5. Полином П является полиномом чётной булевой функции тогда и только тогда, когда 1/(П) является полиномом функции, инвариантной относительно преобразования Мёбиуса.

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

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

Пусть /(хь ...,хп) - булева функция, и т — (тъ... ,тп), где г, е Е2. Пусть т - ненулевой набор, булева функция / называется периодической с периодом т, если /(а^ ф т\,..., хп ф т„) = /(яъ • • ■ > хп)-

В данном разделе доказывается следующее утверждение.

Утверждение 5. Существует детерминированный алгоритм, который, получив на вход запись полинома булевой функции / £ Рг « набора т из нулей и единиц, определяет за полиномиальное время, является ли набор т периодом /.

Приводится конкретный алгоритм для проверки того, что вектор является периодом функции, - алгоритм 3. В диссертации обоснована корректность этого алгоритма в теореме 6.

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

Теорема 7. Пусть набор т е Существует детерминированная двух-ленточная машина Тьюринга, которая по записи полинома булевой функции, поданному ей на вход, определяет, является ли набор т периодом этой функции, со сложностью 0(Я3), где N = 1п, и I - длина полинома функции, а п - число её переменных.

Кроме того, в этом разделе построено в явном виде полиномиальное сведение задачи о поиске периода функции к решению системы алгебраических уравнений (теоремы 8 и 9).

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

Функция f(x i,..., хп) G Pk сохраняет предикат p(yi,..., ут) на Ek, если для любых aj,..., af,..., a*,..., a™ e Ek таких, что

p(a\,..., a™) = 1,..., р{а\,..., a™) = 1

верно p(f(a\, ...,a}n),..., ..., <)) - 1.

Множество всех функций fc-значной логики, сохраняющих предикат р будем обозначать Ак(р). Путь р - m-местный предикат на Ek- Тогда множество Ak{p) - замкнутый класс.

Матрицей предиката называется матрица, столбцами которой являются все наборы(выписанные в произвольном порядке), на которых предикат верен.

В разделе 1 части 2 приведены алгоритмы распознавания сохранения функциями /с-значных логик некоторых одноместных центральных предикатов. Известно, что функция сохраняет одноместный центральный предикат с центром £, тогда и только тогда, когда она сохраняет множество £.

Описание конкретных множеств, сохранение которых может быть распознано, описано в теоремах 10, 11.

Пусть g(x) е Pk, обозначим

Е{д{*)) = {У£ е Ек д{х) = у).

Теорема 10. Для любого простого числа к, любого I е Е*Д{0} и любого г е {1,..., к - 1} существует детерминированная машина Тьюринга, которая с полиномиальной сложностью распознаёт по записи полинома функции f £ Pk, сохраняет ли эта функция множество £ = Е(1хг).

Теорема 11. Для любого простого числа к, любого I € Ек \ {0} и любого i € {1.....к - 1} существует детерминированная машина Тьюринга, которая

с полиномиальной сложностью распознаёт по записи полинома функции / е Рк, сохраняет ли эта функция множество £ = Е(1хг) \ {0}.

Конкретные примеры множеств, сохранение которых можно распознать, используя теоремы 10 и 11, приведены в теоремах 12, 13.

Теорема 13. Для каждого из следующих подмножеств Еь

{0,1}, {0,2}, {0,3}, {0,4}, {0,1,4}, {0,2,3}, {1,4}, {2,3}

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

Теорема 14. Пусть к> 3 - простое число. Для каждого из множеств

{0,1},...,{0,к-1}, {о ,-1,1},{1,-1},1еЕк

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

В разделе 2 части 2 построены полиномиальные алгоритмы для распознавания сохранения функциями ¿с-значных логик некоторых центральных предикатов.

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

(а1 ... ач 0 ... О (XI ... ад ... ад а\ ... а9 0 ... 0

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

Условиям теоремы 20 удовлетворяют предикаты с матрицами вида:

(\ ... к — 1 0 ... 0 1 ... к-1 \1 ... Ы 1 ... ы о ... о

Такие предикаты относятся к классу центральных предикатов. Центральные предикаты интересны тем, что задают предполные классы.

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

Основным результатом раздела 1 третьей части является субэкспоненциальный алгоритм распознавания принадлежности булевой функции, заданной полиномом Жегалкина, классу О2.

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

СВОЙСТВО [¿2.

Класс всех булевых функций, обладающих свойством /л2, будем обозначать О2.

Основной результат раздела сформулирован в теореме 22.

Теорема 22. Существует детерминированная машина Тьюринга, которая по записи полинома булевой функции проверяет, принадлежит ли функция классу О2, причём сложность работы этой машины равна 2°(1о§ где N — 1п, и I - длина полинома функции, ап - число её переменных.

В разделе 2 части 3 приводятся алгоритмы субэкспоненциальные алгоритмы распознавания сохранения функциями трёхзначной логики центральных предикатов с центрами {1} и {2}.

Теорема 23. Существует детерминированная машина Тьюринга, которая по записи полинома функции / е Рк, проверяет, сохраняет ли эта функция двухместный центральный предикат с центром {1}, причём сложность работы этой машины равна где N — 1п, и I - длина полинома

функции, а п - число её переменных.

Теорема 24. Существует детерминированная машина Тьюринга, которая по записи полинома функции / € Рк, проверяет, сохраняет ли эта функция двухместный центральный предикат с центром {2}, причём сложность работы этой машины равна 20(-1о^('М'>\ где N = 1п, и I - длина полинома функции, а п - число её переменных.

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

Теорема 25. Пусть к - постое число, II С Ек,\и\ = т. Тогда существует детерминированная машина Тьюринга, которая по записи полинома функции / € Рк, проверяет, равна ли эта функция 0 на множестве!/11, причём сложность работы этой машины равна 0((тг1п)2), где I - длина полинома функции, г - ранг полинома, ап - число переменных.

Алгоритм из теоремы 25 можно использовать для проверки того, что функция /, заданная полиномом П/, сохраняет множество II = {^1, ... ,ит}. Для этого рассмотрим полином функции

9 =(/- ...(/- ит).

Запись этого полинома имеет длину 0((1п)т), а ранг меньше либо равен тг. И функция / е Рк сохраняет множество С/ тогда и только тогда, когда 5 = 0 на множестве и. Далее применяем теорему 25 для д. Получаем, что проверить сохранение множества С/ функцией /, заданной полиномом, можно со сложностью 0(т2тг(1п)2т), где I - длина полинома функции, ап - число её переменных.

Работы автора по теме диссертации

[1] Бухман A.B. Полиномиальные алгоритмы для распознавания сохранения некоторых множеств функциями, представленными полиномами. Тезисы в материалах 16 международной конференции "ПТК-16". С. 8891. Издательство нижегородского госуниверситета - 2011. - 586 с.

[2] Бухман A.B. О сложности распознавания сохранения функциями многозначных логик, заданных полиномами, некоторых множеств. Вестн. Моск. ун-та. Сер.15. Вычисл. матем. и киберн. 2011. №3. С. 38-43.

[3] Бухман A.B. Об эффективно функционально разрешимых классах в трёхзначной логике. Материалы 8 молодёжной научной школы по дискретной математике и её приложениям. С. 13-18. Часть I. Под редакцией A.B. Чашкина - 2011. - 56 с.

[4] Бухман A.B. Об одном алгоритме распознавания сохранения множества полиномами малого ранга. Тринадцятий М1жвуз1вський науково-практичний семшар Комбшаторш конфЬурацп та ix застосування. С. 21-25. Юровоград - 2012. - 180 с.

[5] Бухман A.B. Полиномиальный алгоритм распознавания функций, инвариантных относительно преобразования Мёбиуса. Одиннадцатый международный научный семинар "Дискретная математика и ее приложения", посвященный 80-летию со дня рождения академика О. Б. Лупано-ва. С. 188-190. М.:Изд-во механико-математического факультета МГУ - 2012. - 453 с.

[6] Бухман A.B. О применении обобщенных полиномов для построения алгоритмов распознавания свойств fc-значных функций, заданных полиномами, Дискрет, матем., 24:3. 2012. С. 51-61.

[7] Бухман A.B. Субэкспоненциальный алгоритм распознавания принадлежности булевой функции, заданной полиномом, одному классу Поста. Тезисы докладов научной конференции "Тихоновские чтения". С. 45 М.: МАКС Пресс - 2012 - 76 с.

[8] Бухман A.B. О распознавании функций, инвариантных относительно преобразования Мёбиуса, и чётных функций, заданных в форме полиномов. Прикладная математика и информатика. 2012. №41, С. 105-112.

[9] Бухман A.B. О сложности распознавания периодичности булевых функций. заданных полиномами. Сборник тезисов XX Международной научной конференции студентов, аспирантов и молодых учёных "JIOMOHOCO 2013" (секция вычислительная математика и кибернетика) С. 46-48. М.: МАКС Пресс - 2013 - 156 с.

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

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

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

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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В. Ломоносова

ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ

04201362950 на правах рукописи

БУХМАН АНТОН ВЛАДИМИРОВИЧ

ОБ АЛГОРИТМИЧЕСКОЙ СЛОЖНОСТИ РАСПОЗНАВАНИЯ СВОЙСТВ ДИСКРЕТНЫХ

ФУНКЦИЙ, ЗАДАННЫХ ПОЛИНОМАМИ

ДИССЕРТАЦИЯ

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

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

МОСКВА, 2013

Оглавление

Введение ....................................................................2

Основные определения...........................10

1. Распознавание свойств булевых функций.............13

1. Распознавание инвариантности относительно преобразования Мёбиуса........................13

2. Распознавание чётности функции .............21

3. Связь чётности и инвариантности относительно преобразования Мёбиуса......................28

4. Распознавание периодичности................29

2. Сохранение предикатов функциями многозначной логики .... 43

1. Некоторые одноместные центральные предикаты.....44

2. Применение обобщённых полиномов к задаче распознавания сохранения функцией предикатов..........51

3. Неполиномиальные алгоритмы...................64

1. Проверка принадлежности функций, заданных полиномами, одному классу Поста.................64

2. О распознавании сохранения некоторых двухместных центральных предикатов функциями из Рз..........66

3. Об одном алгоритме распознавания сохранения множества полиномом малого ранга................71

Заключение.................................75

Приложение 1 ...............................76

Литература.................................78

Введение

Дискретные функции являются одним из основных объектов исследовании в математике [28]. Интерес к ним вызван тем, что они имеют ряд приложений на практике. Например, дискретные функции используются в синтезе СБИС [29], кодировании [22], анализе программ [16], криптографии [21] и других прикладных областях.

Среди дискретных функций можно выделить класс булевых функций. Эти функции возникли из логики [36, 37]. Для них можно рассмотреть операцию суперпозиции. Множество булевых функций с введённой на нем операцией образует алгебру - так называемую булеву алгебру (или алгебру логики) [30]. При таком подходе основными вопросами теоретических исследований становятся проблемы полноты, выразимости и представления. Первые результаты для булевых функций как алгебраических объектов были получены Э. Постом (Е. Post) в [39, 40]. В этих работах Постом были описаны все замкнутые классы булевых функций, в частности, был получен критерий полноты системы функций. Этот критерий утверждает, что система полна тогда и только тогда, когда целиком не лежит ни в одном из конечного числа предполных классов.

После изучения Постом булевых функций, возник вопрос об исследовании их естественного обобщения - функций многозначных логик. Среди ранних работ по этой тематике можно отметить [18, 28, 33] и другие. C.B. Яблонским [28] были описаны все предполные классы функций трёхзначной логики. А.И. Кузнецов [18] получил критерий полноты для функций многозначных логик, который утверждал, что существует конечное число предполных классов. Некоторые предполные классы были описаны в работах [28, 23, 41]. И окончательное описание всех предполных классов в /с-значпой логике дал Розенберг [42, 43].

Отметим, что все перечисленные результаты являются теоретическими в том смысле, что булевы функции рассматриваются как абстрактный объект и не приводятся никакие эффективные методы проверки принадлежности функций тем или иным классам (кроме работы [18]). Поэтому, для того чтобы па практике использовать результаты из [28, 42, 43], надо построить эффек-

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

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

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

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

обладает свойством, если предикат на ней истинен, иначе - она не обладает свойством.

Задачи, где требуется, чтобы функции обладали определёнными свойствами, часто встречаются, например, в криптографии. Для построения некоторых шифров надо, чтобы функция имела свойства, которые бы гарантировали стойкость шифра. К таким свойствам относятся совершенная уравновешенность, обладание функцией линейной структурой и другие [8, 21]. Свойства булевых функций можно также использовать для решения задачи о полноте некоторой конечной системы функций. Дело в том, что проверка полноты системы проводится проверкой принадлежности каждой из функций этой системы предполным классам [39, 18]. Любой предполный класс функций конечнозначных логик можно описать как множество функций, обладающих свойством сохранять предикат [42, 43]. Поэтому вопрос о полноте системы функций сводится к вопросу проверки свойств функций этой системы. Рассмотрим ещё один пример использования свойств дискретных функций. Очень многие практически важные задачи являются КР-полными или ИР-трудными (например, выполнимость КНФ, решение систем алгебраических уравнений над конечным полем [11]). Поэтому на практике получили широкое распространение исследования, в которых выясняется, при каких ограничениях па исходную задачу, она имеет полиномиальное решение. Т. Шефер (Т.Л. 8сЬас!ег) в работе [44] показал, каким свойствам должна удовлетворять система функций, чтобы задача выполнимости над ней была разрешима за полиномиальное время.

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

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

ритмической сложности. Для исследования поведения реальных вычислителей в теории сложности рассматриваются модели исполнителей алгоритмов (например, машина Тыорипга, RAM-машина и т.д. [7]). На практике одним из важнейших вычислительных ресурсов для реальных ЭВМ является время выполнения алгоритма. В теории алгоритмической сложности вводится специальное понятие - временная сложность работы алгоритма в худшем случае [11]. Так как алгоритм предназначен для работы на счётном наборе данных, то временная сложность (или просто время работы) рассматривается как функция от длины входа. В теории сложности принято считать, что алгоритм для некоторой задачи будет эффективен на практике, если его временная сложность есть полином от длины входа. Некоторые объяснения такого подхода можно найти [3, 11, 7]. Алгоритмы с полиномиальной временной сложностью обладают следующей особенностью. Если есть полиномиальный алгоритм для решения некоторой задачи в одной из основных моделей теории сложности (машина Тыоринга, машина Тыорипга с q лептами, RAM-машина), то и для любой другой модели можно построить полиномиальный алгоритм [11, 7]. Имеется большое количество статей и монографий, в которых исследуется вопрос о построении полиномиальных алгоритмов для решения конкретных задач [34, 11]. Много исследований посвящено задачам распознавания. В теории сложности есть класс Р - задач распознавания, разрешимых за полиномиальное время па детерминированной машине Тыоринга. Пусть у нас имеется свойство функции р. Задача проверки по функции того, что она обладает свойством р, является задачей распознавания.

В данной работе рассматривается следующая задача. Пусть есть некоторое свойство функций многозначной логики. Требуется построить полиномиальный алгоритм для проверки того, что функция, поданная алгоритму в виде полинома, обладает данным свойством. Задача построения алгоритмов для распознавания свойств дискретных функций исследовалась в ряде работ. Случай, когда функция подаётся на вход алгоритма в виде вектора значений, был рассмотрен в работах В.Б. Алексеева, Н.Р. Емельянова, A.A. Воронеико и др. [3, 5, 45]. В этих работах исследовались свойства функций, касающиеся полноты систем, и в качестве алгоритмической модели рассматривались последовательности СФЭ. Распознавание свойств функций в случае, когда

алгоритм получает на вход полином был рассмотрен в работах С.П. Горшкова, С.Н. Селезневой, М.Н. Вялого [25, 26, 10, 9]. В работах С.Н. Селезневой [25, 26] получены полиномиальные алгоритмы для проверки свойств, связанных с полнотой системы дискретных функций. В частности в [25] был описан полиномиальный алгоритм для распознавания полноты системы булевых функций. В [26] построены полиномиальные алгоритмы для распознавания свойства сохранения функциями некоторых семейств предикатов, описанных в работах Розеиберга [42, 43]. Результаты работы [10] связаны с распознаванием свойства принадлежности булевых функций классам Шсфера. В этой работе рассматривались различные способы задания функций, и в частности, полиномы. Были получены полиномиальные алгоритмы для проверки принадлежности булевых функций, заданных полиномами, всем классам Шефе-ра.

В настоящей работе доказаны результаты являющиеся продолжением исследований начатых в [25, 26, 27,10]. Здесь рассмотрены следующие свойства:

1. Инвариантность относительно преобразования Мёбиуса. Данное свойство описывает класс интересных с точки зрения теории и приложений функций. О применении этого свойства рассказано в работах [19, 38].

2. Чётность функции. Данное свойство важно для задачи распознавания полноты. Полиномиальный алгоритм его распознавания был предложен ещё С.Н. Селезневой в [25]. Здесь построен алгоритм, имеющий меньшую сложность.

3. Периодичность функции. Это свойство в некоторой степени обобщает свойство чётности. Оно интересно с точки зрения изучения инвариантности функций относительно простейших линейных преобразований аргументов и обладания линейной структурой [21].

4. Сохранение функцией предикатов. Данное свойство описывает замкнутые классы [32].

Цель работы.

Целыо работы является построение быстрых алгоритмов для решения задач распознавания следующих свойств булевых функций: чётности, инвариантности относительно преобразования Мёбиуса и периодичности. А также построение быстрых алгоритмов распознавания сохранения /с-зпачными

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

Научная новизна и выносимые на защиту положения.

Все основные результаты диссертации являются новыми. Основные результаты выносимые на защиту:

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

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

Вклад автора.

Все результаты, вынесенные на защиту, принадлежат автору.

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

Все результаты диссертации опубликованы в работах [47, 48, 49, 51, 52, 53, 54, 55, 56]. Среди них работы [48, 53] в журналах списка ВАК.

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

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

• VIII молодёжная научная школа по дискретной математике и её приложениям (Москва, 24-29 октября 2011);

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

• Научная конференция "Тихоновские чтения 2012" (Москва, 29-31 октября 2012);

Структура диссертации.

Работа состоит из введения, раздела с основными понятиями, трёх основных частей, заключения, приложения и списка литературы. В разделе "Основные определения" вводятся определения и обозначения, которые используются в тексте диссертации. Первая часть диссертации разбита на 4 раздела. В первом разделе построен полиномиальный алгоритм распознавания инвариантности булевых функций, заданных полипомами, относительно преобразования Мёбиуса. Во втором разделе построен полиномиальный алгоритм распознавания чётности булевых функций, заданных полиномами. В третьем разделе исследуется связь между двумя классами функций (чётными и инвариантными относительно преобразования Мёбиуса). В четвёртом разделе построены полиномиальные алгоритмы для распознавания периодичности булевых функций, исследованы свойства полиномов периодических функций и построено полиномиальное сведение задачи поиска периода функции к задаче решения системы уравнений.

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

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

циальный алгоритм проверки того, что трёхзначная функция, заданная полиномом, сохраняет двухместный центральный предикат с центром {1} (и с центром {2}.) В третьем разделе приводится один алгоритм проверки свойства функции, заданной полиномом, сохранять множества, этот алгоритм эффективен для полиномов малого ранга.

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

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

Основные определения

Пусть к >2 - натуральное число, Е^ = {0,..., к — 1}. Ф