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

• Бухман, Антон Владимирович
• кандидат физико-математических наук
• 2013

Оглавление диссертации кандидат физико-математических наук Бухман, Антон Владимирович

Оглавление

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

Приложение 1

Литература

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

Введение

Дискретные функции являются одним из основных объектов исследовании в математике [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].

Цель работы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• 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).

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

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

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

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

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

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

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

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

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

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

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

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Бухман, Антон Владимирович

Основные результаты, полученные в диссертации.

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

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

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

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

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

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Бухман, Антон Владимирович, 2013 год

Литература

Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел: Пер. с англ. - М.: Мир - 1987. - 416 с.

Артюхов В.Л., Копейкин Г. А., Шалыго А. А. Настраиваемые модули для управляющих логических устройств. Ленинград: Энергоиздат - 1981. -166 с.

Алексеев В.Б. Введение в теорию сложности алгоритмов. М: Изд. отд. ф-та ВМиК МГУ - 2002. - 82 с.

Алексеев В.Б., Емельянов Н. Р. Метод построения быстрых алгоритмов в /с-значной логике, Матем. заметки, 38:1, 1985. С. 148-156

Емельянов Н.Р. Об одном подходе к построению эффективных алгоритмов распознавания полноты в многозначных логиках, Матем. заметки, 39:5, 1986. С. 766-775

Ачасова С. М. Алгоритмы синтеза автоматов на программируемых матрицах. М.: Радио и связь - 1987. - 135 с.

Ахо А., Хопкофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир - 1979.

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

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

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

функции. Обозрение прикл. и промышленной матем. Сер. Дискр.матем. 1997, 4, №2, С. 216-237.

[11] Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. Пер. с англ. М.: Мир - 1982. - 419 с.

[12] Дирихле П.Г.Л. Лекции по теории чисел. В обработке и с добавлениями Р.Дедекинда. Пер. с нем. Изд.З, стереот. 2009.

[13] Жегалкин И. И. О технике вычислений предложений в символической логике. Матем. сб. 1927, 34, С. 9-28.

[14] Жегалкин И. И. Арифметизация символической логики. Матем. сб. 1928, 35, №3-4.

[15] Кириченко К. Д. Верхняя оценка сложности полиномиальных нормальных форм булевых функций. Дискрет, матем., 17:3. 2005. С. 80-88

[16] Кнут Д. Искусство программирования, том 4, А. Комбинаторные алгоритмы, часть 1 = The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. - M.: Вильяме - 2013. - 960 с.

[17] Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ = Introduction to Algorithms. - М.: Вильяме - 2005. - 1296 с.

[18] Кузнецов A.B. О проблемах тождества и функциональной полноты алгебраических систем. В кн. Труды 3-го всесоюзного матем.съезда, т.2. М.: изд. АН СССР - 1956. С. 145-146.

[19] Леонтьев В.К. О некоторых задачах, связанных с булевыми полиномами. Журнал вычислительной математики и математической физики. 1999, 9, №6. С. 1045-1054.

[20] Лидл Р., Нидеррайтер Г. Конечные поля:В 2-х т. Т.2. Пер. с англ. - М.: Мир - 1988. - 822 с.

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

[22] Мак-Вильямс Ф. Дж., Слоэн Ii. Дж. А. Теория кодов, исправляющих ошибки. М.: Радио и связь - 1979. - 743 с.

[23] Мартышок В.В. Исследование некоторых классов в многозначных логиках. Проблемы кибернетики. 1960, 3. С. 49-60.

[24] Перязев H.A. Основы теории булевых функций. - М.:ФИЗМАТЛИТ, 1999. - 112 с.

[25] Селезнева С.Н. О сложности распознавания полноты множества булевых функций, реализованных полиномами Жегалкина. Дискретная математика. 1997, 9:4. С. 24-31.

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

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

[28] Яблонский C.B. Функциональные построения в к-значной логике. Сбор-пик статей по математической логике и ее приложениям к некоторым вопросам кибернетики, Тр. МИАН СССР, 51, М.: Изд-во АН СССР -1958. С. 5-142

[29] Яблонский C.B. Элементы математической кибернетики. М.: Высшая школа, 2007.

[30] Яблонский C.B. Введение в дискретную математику. М.:Высшая школа, 2010. - 384 с.

[31] Яблонский C.B., Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры логики и классы Поста. М.:Наука, 1966 - 120 с.

[32] Яблонский C.B., Гаврилов Г.П., Набебин A.A. Предполные классы в многозначных логиках. М.: Изд-во МЭИ, 1997 - 144 с.

[33] Янов Ю.И., Мучник A.A. О существовании /с-значных замкнутых классов, не имеющих конечного базиса. - ДАН СССР, 1959, 127, №1. С. 44-46.

[34] Agrawal Manindra, Kayal Neeraj, Saxena Nitin. PRIMES is in P. Annals of Mathematics 160 (2). P. 781-793. 2004.

[35] Bettale L., Faugere J., Perret L. Hybrid approach for solving multivariate systems over finite fields. In Journal of Mathematical Cryptology (2009) №3, P. 177-197.

[36] Boole G. (1854). An Investigation of the Laws of Thought on Which are Founded the Mathematical Theories of Logic and Probabilities. Macmillan. Reprinted with corrections, Dover Publications, New York, NY, 1958.

[37] Boole G. (1847) The Mathematical Analysis of Logic. In e-library www.gutenberg.org/ebooks/36884.

[38] Pieprzyk J., Zhang X.-M. Computing mobius transforms of boolean functions and characterising coincident boolean functions // Boolean Functions: Cryptography and Applications. France, Rouen: Publications des Universites de Rouen et du Havre, 2007. P. 135-151

[39] Post E. Introduction to a general theory of elementary propositions. Amer. Journ. Mathem. 1921. 43, P. 165-185.

[40] Post E. Two-valued iterative systems. 1941.

[41] Lo Czu Kai. Precompleteness of a set and rings of linear functions. Acta bf. natur Univ. Jilinesis (1963) 2.

[42] Rosenberg I. La struct des fonctions de plusieurs variables sur un ensemble fini/ Comptes Rendus? de lÄcadem. Paris (1965) 260, 3817-3819.

[43] Rozenberg I. Uber die funktionale Vollständigkeit in der mehrvertigen Logiken. Rozpravy Cescko-slovenskë Academie vd. Rada matematickych a prirodnich vëd. Praga, 1970, rocnic 80, Sesit 4. P. 3-93.

[44] Schaefer T.J. The complexity of satisfiability problems. In: Proceedings 10th Symposium on Theory of Computing. P. 216-226. ACM Press, New York, 1978.

[45] Voronenko 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.

[46] Wolf C., Thomae E. Small Linearization: Memory Friendly Solving of NonLinear Equations over Finite Fields. IACR Cryptology ePrint Archive. 2011. P. 669-669.

Публикации автора.

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

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

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

[50] Бухман А.В. Алгоритмы распознавания сохранения /с-зпачпыми функциями, заданными полиномами, подмножеств мощности к — 1. Материалы конференции "Математика и безопасность информационных технологий". С. 112-117. М.:МАКС Пресс - 2012. - 136 с.

[51] Бухман А.В. Об одном алгоритме распознавания сохранения множества полиномами малого ранга. Тринадцятий Міжвузівський науково-практичний семінар Комбінаторні конфігурації та іх застосування. С. 21-25. Кіровоград - 2012. - 180 с.

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

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

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

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

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