Введение к работе
Актуальность темы.
В диссертационной работе рассматриваются вопросы, связанные с распознаванием конкретных свойств функций булевой и многозначных логик. Основные результаты диссертации состоят в построении полиномиальных алгоритмов для проверки того, что функция (булева или многозначной логики), поданная на вход алгоритма в виде полинома, обладает некоторым, заранее известным свойством. Эта тематика актуальна с теоретической и практической точек зрения. Теоретический результат состоит в том, что доказана принадлежность классу Р ряда задач. На практике встречаются задачи, для которых требуется использовать дискретные функции, обладающие определёнными свойствами. Под свойством мы будем понимать предикат (эффективно вычислимый), который действует на множестве функций /с-значной логики. Будем считать, что функция обладает свойством, если предикат на ней истинен, иначе - она не обладает свойством.
Задачи, где требуется, чтобы функции обладали определёнными свойствами, часто встречаются, например, в криптографии. Для построения некоторых шифров надо, чтобы функция имела свойства, которые бы гарантировали стойкость шифра. К таким свойствам относятся совершенная уравновешенность, обладание функцией линейной структурой и другие1'2. Задача построения алгоритмов для распознавания свойств дискретных функций исследовалась в ряде работ. Случай, когда функция подаётся на вход алгоритма в виде вектора значений, был рассмотрен в работах В.Б. Алексеева3, Н.Р. Емельянова , АА. Вороненко5 и др. В этих работах исследовались свойства функций, касающиеся функциональной полноты систем, и в качестве алгоритмической модели рассматривались последовательности СФЭ. Распозна-
1 Логачев О., Сальников А., Смышляев С, Ященко В. Булевы функции в теории кодирования и криптологии. 2-е изд., дополн. М.: МЦНМО, 2012.
2Ван Тилборг X. Основы криптологии. М.:Мир - 2006. - 471 с.
3Алексеев В.Б., Емельянов Н. Р. Метод построения быстрых алгоритмов в /г-значной логике, Матем. заметки, 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. Результаты СП. Горшкова связаны с распознаванием свойства принадлежности булевых функций классам Шефера. В этой работе рассматривались различные способы задания функций, и в частности, полиномы. Были получены полиномиальные алгоритмы для проверки принадлежности булевых функций, заданных полиномами, всем классам Шефера.
Цель диссертационной работы.
Целью работы является построение быстрых алгоритмов для решения задач распознавания следующих свойств булевых функций: чётности, инвариантности относительно преобразования Мёбиуса и периодичности. А также построение быстрых алгоритмов распознавания сохранения /с-значными функциями некоторых центральных предикатов (при простых значениях к). Также в работе ставилась цель исследовать особенности полиномов функций,
е Горшков СП. О сложности распознавания мультиаффинности, биюнктивности, слабой положительности и слабой отрицательности булевой функции. Обозрение прикл. и промышленной матем. Сер. Дискр.матем. 1997, 4, №2, С. 216-237.
7Селезнева С.Н. О сложности распознавания полноты множества булевых функций, реализованных полиномами Жегалкина. Дискретная математика. 1997, 9:4. С. 24-31
8Селезнева С.Н. Полиномиальный алгоритм для распознавания принадлежности реализованной полиномом функции /г-значной логики предполным классам самодвойственных функций. Дискретная математика. 1998, 10:3. С. 64-72.
9Селезнева С.Н. Полиномиальный алгоритм распознавания свойства функций многозначных логик, представленных полиномом, сохранять рефлексивный и транзитивный предикат. Тезисы докладов XII Международной конференции "Проблемы теоретической кибернетики" (Нижний Новгород, 1999). М.:МГУ, 207.
10Вялый М.Н. Алгоритмические задачи с таблицами значений булевых полиномов. Труды ИСП РАН, т.6, 2004. С. 51-64.
11 Rosenberg I. La struct des fonctions de plusieurs variables sur un ensemble fini/ Comptes Rendus? de lAcadem. Paris (1965) 260, 3817-3819.
12Rozenberg I. Uber die funktionale Vollstandigkeit in der mehrvertigen Logiken. Rozpravy Cescko-slovenske Academie vd. Rada matematickych a prirodnich ved. Praga, 1970, rocnic 80, Sesit 4. P. 3-93.
обладающих перечисленными выше свойствами. Методы иследования.
Для получения результатов диссертации применялись методы теории дискретных функций, алгебраические и комбинаторные методы, а также методы теории конечных полей, теории чисел и методы линейной алгебры.
Научная новизна.
Основные результаты диссертационной работы заключаются в следующем:
-
Построены полиномиальные алгоритмы распознавания по полиномам булевых функций свойств инвариантности относительно преобразования Мёбиуса и периодичности.
-
Улучшена оценка сложности алгоритма распознавания чётности булевых функций, заданных полиномами.
-
Построено явное полиномиальное сведение задачи поиска периода булевой функции, заданной полиномом, к решению системы алгебраических уравнений.
-
Получены полиномиальные алгоритмы для распознавания сохранения функциями, заданными полиномами, одного класса центральных предикатов.
-
Построены субэкспоненциальные алгоритмы проверки принадлежности функций, заданных полиномами, некоторым замкнутым классам.
Основные результаты работы являются новыми и получены лично автором.
Практическая ценность.
Работа носит теоретический характер. Полученные результаты могут быть применимы при построении алгоритмов на реальных вычислительных машинах для распознавания свойств функций, рассмотренных в диссертации.
Апробация.
Результаты диссертации докладывались на следующих конференциях:
Международная конференция "Проблемы теоретической кибернетики 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 страницы машинописного текста.
