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

Введение к работе

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

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

Среди характеристик любого математического объекта важное значение имеют его количественные характеристики. Для классов дискретных функций одной из наиболее важных таких характеристик является число f (п) функций в' классе, зависящих от п фиксированных переменных. Это число р(п) конечно для любого класса k-значных или частичных к-значных функций. Кроме непосредственной количественной характеризации данного класса функция <р{п) характеризует сложность алгоритмов, связанных с перебором функций данного класса, минимальную длину кодов для кодирования всех функций данного класса, зависящих от п переменных. Как показал О.Б. Лупанов, наибольшая сложность схем, реализующих булевы функции из некоторого класса зп, связана с асимптотикой логарифма числа функций в зл, зависящих от п переменных. Исследования показывают, что не только установление точной формулы, но даже получение достаточно хороших оценок для р(п), в большинстве случаев представляет собой трудную задачу.

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

оказалась очень трудной. Эта задача была поставлена еще Дедекиндом в 1897 г. как проблема вычисления числа свободных дистрибутивных структур с п образующими. В 1963г. Коробков установил порядок при п -> « для log₂iMn), где 0(п) - число монотонных булевых функций. В 1966 г. Ж. Ансель улучшил оценки для log₂0(n), но не смог получить асимптотику для 1од₂!Д(п). В 1969 г. Д.Клейтмен получил асимптотику для log-Фіп). И только в 1977 г. Коршунов Л.Д. установил асимптотику для ф[п). Позднее более простое доказательство асимптотической формулы для ф(п) получил Сапоженко А.А.

Другим примером , может служить проблема оценки числа пороговых булевых функций от п переменных. Для этой задачи, активно исследовавшейся в разных странах еще в 60-х годах нашего столетия, только в 1989 году Зуевым Ю.А. была установлена асимптотика логарифма числа пороговых функций.

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

Если перейти к рассмотрению классов k-значных функций при к*з или частичных k-значных функций при к*2, то оказывается, что даже установление асимптотики log (п) - число функций в классе от п переменных, во многих случаях представляет собой трудную задачу. Так, например, в работах Коробкова В.К., который рассматривал задачу оценки числа монотонных k-значных функций, получен только порядок логарифма числа таких функций. Таким образом, возникает необходимость разработки методов, применимых для широкого круга задач оценки числа дискретных функций.

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

все функции из Р_к или Р_к>

Впервые вопрос такого типа был рассмотрен, по-видимому, Р.В. Фрейвалдом (см. Трахтенброт Б. А. Сложность алгоритмов и вычислений (Спецкурс для студентов НГУ)// НГУ, Новосиб., 1967, стр. 243-249) . Он рассмотрел задачу о сложности распознавания полноты системы булевых функций на машине Тьюринга при условии, что функции представляются на ленте машины строками их значений с разделителем. В соответствии с теоремой Поста, для распознавания полноты системы, булевых функций достаточно проверить принадлежность данных функций пяти классам. Фрейвалд показал, что для каждого из этих классов это можно сделать на

машине Тьюринга с числом операций o(N ), где N -длина входа, и для распознавания полноты эта оценка неулучшаема по порядку.

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

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

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

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

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

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

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

ОбЪеКТОВ;

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

1. с использованием метода искусственных ограничений получена асимптотика при к-*» логарифма числа простых базисов в частичной k-значной логике,-

2. с использованием метода искусственных ограничений получена асимптотика логарифма числа различных замыканий на n-элементном множестве,-

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

полукольцами;

6) для использования в методе полилинейных форм разработан
метод ускорения вычислений тензорных степеней полилинейных форм,
основанный на ступенчатых билинейных разложениях,-

7) с использованием метода полилинейных форм получен
алгоритм (в модели неветвящихся алгоритмов) для распознавания
полноты систем функций в 7-значной логике с битовой сложностью
0(N ' ), где N - суммарная длина векторов значений всех данных

функций (естественный алгоритм имеет сложность 0(N )) и алгоритм для распознавания полноты систем функций в частичной 2-значной

log 3 логике с битовой сложностью 0(n -logN-loglogN-logloglogN)

(естественный алгоритм имеет сложность 0(N )). Получены также

нетривиальные результаты о сложности распознавания полноты

систем функций в k-значной логике при больших к.

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

Апробац,ия_работьі. Результаты диссертации докладывались на международной конференции по основам теории вычислений (Казань, 1987), на международной конференции^- по методам теории чисел и алгебры в компьютерных науках (Москва, 1993), на международном семинаре по сложности и реализации булевых функций (Дагштул, ФРГ, 1992), на советско-германских семинарах по дискретной математике (Самарканд, 1987, Росток, 1988, Ереван, 1989), на всесоюзных конференциях по проблемам теоретической кибернетики (Новосибирск, 1980, Горький, 1988, Волгоград, 1990), на всесоюзных и межгосударственных семинарах по дискретной математике и ее -приложениям (Москва, 1987, 1990, 1995), на Ломоносовских чтениях в МГУ, на семинарах по математическим вопросам кибернетики под руководством чл.-корр. РАН С.В.Яблонского и семинарах по синтезу управляющих систем и смежным вопросам под руководством чл.-корр. РАН О.Б.Лупанова и с.н.с. В.М.Храпченко, на других конференциях, школах и

семинарах.

Публикации. Основные результаты диссертации опубликованы в работах [1-22] , список которых приводится в конце автореферата.

СтЕуктуЕа_и_объем_р_абдты. Диссертация состоит из введения, двух глав и списка литературы. Первая глава разбита на 9 параграфов, вторая - на 6. Объем работы 247 страниц. Список литературы содержит 9 8 наименований.