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

• Автор: Шабанин, Олег Васильевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2000
• Место защиты: Москва
• Количество страниц: 70 с.

Глава!. Оценка сложности дизъюнктивной нормальной формы пороговых функций.

§1.0 связи числа нижних единиц пороговой функции с

коэффициентами вектора Чоу

§ 2. Оценка сложности дизъюнктивной нормальной формы

пороговой функции в “типичном” случае

Глава 2. Оценки сложности многочлена Жегалкина пороговой функции.

§1.0 связи длины многочлена Жегалкина булевой функции с числом нижних единиц. Оценка.дой&иууцюгочлена Жегалкина

; . V ; • >~

пороговой функции в “типич0ом’*8Й5*йе . . .

§ 2. Оценка степени многочлена Жегалкина пороговой

функции
Глава 3. Оценки расстояний между классами обобщенномонотонных и линейных функций. Декомиозируемость самодвойственных пороговых функций.
§ 1. Оценки расстояний между классами обобщенно-монотонных
и линейных функций
§ 2. Некоторые неравенства для коэффициентов Чоу пороговых
функций
§ 3. Декомиозируемость самодвойственных пороговых
функций
Заключение
Список литературы

Диссертация посвящена исследованию параметров сложности двоичных пороговых функций. Получены принципиально новые экспоненциальные асимптотические оценки длины кратчайшей дизъюнктивной нормальной формы (д.н.ф.) и длины многочлена Жегалкина для почти всех пороговых функций. Впервые доказаны нетривиальные нижние оценки степени многочлена Жегалкина произвольной пороговой функции. Изучены вопросы оценок и нахождения расстояний от класса линейных до класса пороговых функций. Приведены необходимые и достаточные условия функциональной разделимости самодвойственной пороговой функции.
Интерес к теории сложности стимулируется вычислениями на ЭВМ. Основные результаты по теории сложности связаны с именами К. Шеннона, С.В. Яблонского, ОБ. Лупанова, Ю.И. Журавлева, Р.Г. Нигматуллина, А.Д. Коршунова А.Д. и ряда других авторов. Достаточно полный обзор результатов по теории сложности представления булевых функций в различных базисах из функциональных элементов можно найти в работе Р.Г. Нигматуллина “Сложность булевых функций”. Оценка сложности д.н.ф. пороговых функций представляет теоретический и практический интерес. Хорошо известен факт, что
пороговых функций от п переменных имеет мажоритарная функция. Большая сложность реализации пороговых функций в “традиционных” базисах служит аргументом для использования в ряде случаев пороговых представлений булевых функций вместо
наибольшую сложность д.н.ф., равную
в классе

представлений в виде д.н.ф. С другой стороны, исследование сложности д.н.ф. пороговых функций тесно связано с проблемой алгоритмической сложности № - полных задач. Например, с известной задачей о ранце, имеющей естественную экономическую интерпретацию и тесно связанную с задачами линейного программирования. Изучение строения множество нулей монотонной пороговой функции может дать ответ на проблему алгоритмической сложности решения этой задачи. Отдельной задачей является получение оценок сложности д.н.ф. для “почти всех” пороговых функций.
Задача оценки сложности д.н.ф. типичной пороговой функции предложена Ю.А. Зуевым. Наилучшая известная нижняя оценка получена в работе Ю.А. Зуева и Л. И. Лип кина, где доказано, что почти у всех пороговых функций сложность д.н.ф. не меньше п2/og2KОценки расстояний между монотонными и линейными функциями имеют как теоретический, так и практический интерес, связанный с потребностями теории кодирования и прикладными вопросами идентификации функций. При решении различных задач применяется метод линеаризации -приближения произвольной булевой функции линейной. С этой точки зрения расстояние по Хеммингу до ближайшей линейной функции также служит мерой сложности функции / Постановку задачи и подходы к решению можно найти в работе Балакина Г.В. и Никонова В.Г. “Методы сведения булевых уравнений к системам пороговых соотношений” (Обозрение прикладной и промышленной математики, 1994 г. - т.1, вып. 3. с. 389 - 401).

§2. Некоторые неравенства для коэффициентов Чоу пороговых
функций.
Как отмечалось выше, коэффициенты Чоу пороговой функции f(xx xn) непосредственным образом связаны с расстоянием от функции / до линейных функций, зависящих от одной переменной, а именно
4(/) = 2"_1 -d{f,xt).
Из того факта, что булевы функции, являющиеся константами, а также существенно зависящие от одной переменной, являются пороговыми, следует, что каждый из коэффициентов Чоу Д0(/),Л„(/) пороговой функции /(х хи) может принимать значения в интервале от -2"'1 до
Пример линейной булевой функции, существенно зависящей от двух и более переменных, показывает, что коэффициенты Дс (/), А, А,,(/) одновременно могут быть равны нулю. Покажем, что для пороговой функции хй)
сумма абсолютных значений коэффициентов Чоу больше либо равна 2”
ТЕОРЕМА 3.2.1.
Для любой пороговой функции g(x xn) выполняется неравенство
|4fe)l+|A1fe!+. ..|A4g|fe2« (1)
При этом равенство достигается лишь в случае, когда = X,, либо ,хя)= const.