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

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

ОКОЛЬНИШНИКОВА Елизавета Антоновна

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

специальность 01 01 09 — дискретная математика и математическая кибернетика

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

Новосибирск — 2007

Работа выполнена в Институте математики им С Л Соболева СО РАН РФ

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

доктор физико-математических наук, профессор

Аблаев Фарид Мансурович доктор физико-математических наук, профессор

Мошков Михаил Юрьевич доктор физико-математических наук, профессор Шоломов Лев Абрамович

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

механико-математический факультет Московского государственного университета им М В Ломоносова

Защита состоится 24 октября 2007 г в /Г час О ^'мин на заседании диссертационного совета Д 003 015.01 при Институте математики им. С. Л Соболева СО РАН 630090, г Новосибирск, пр Академика Коптюга, 4, к 417

С диссертацией можно ознакомиться в библиотеке Института математики им С Л Соболева СО РАН

Автореферат разослан " " сентября 2007 г

Ученый секретарь диссертационного совета д ф -м н

Ю В Шамардин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Теория сложности вычислений является важным разделом математической кибернетики Целью теории является оценивание величины ресурсов, необходимых для решения тех или иных вычислительных задач. Рассматриваются различные модели вычисления такие, например, как машины Тьюринга, автоматы, нормальные алгоритмы, схемы из функциональных элементов, формулы в различных базисах и т д В качестве оцениваемых ресурсов рассматриваются время вычисления, объем используемой памяти, длина программы и др Под сложностью вычисления понимается величина этого ресурса При этом сложность зависит как от модели вычислений, так и от выбранного оцениваемого ресурса Основным объектом теории является получение верхних и нижних оценок сложности При этом получение нижних оценок сложности в большинстве рассматриваемых моделях вычислений представляет наибольшую трудность Это объясняется тем, что при установлении нижних оценок сложности надо в той или иной мере просмотреть все возможные способы вычисления рассматриваемого объекта и показать, что вычислить этот объект с меньшими затратами невозможно При получении нижних оценок сложности возникают, решаются и используются важные и интересные задачи из различных областей дискретной математики

Известно [2, 4, 5, 18, 19], что во многих моделях вычисления, таких как схемы из функциональных элементов, контактные схемы, формулы в конечных базисах, ветвящиеся программы, почти все булевы функции вычисляются очень сложно (экспонента от числа переменных функции), тем не менее, лишь для небольшого числа полностью определенных булевых функций доказано, что их нельзя вычислить с

^Важным понятием в теории сложности является также сложность объектов по Колмогорову, введенная в [3] для алгоритмического определения понятия количества информации

линейной сложностью (для схем из функциональных элементов удалось получить лишь линейные оценки) относительно числа переменных булевой функции. К этому направлению относятся работы А А Разборова [8] и А Е Андреева [1], в которых были получены сверхполиномиальные2-1 нижние оценки сложности для схем из функциональных элементов в монотонном базисе, реализующих известные функции

Сложность вычисления булевой функции зависит от модели вычисления Так, например, линейная булева функция вычисляется с линейной сложностью в классе схем из функциональных элементов, контактных схем, ветвящихся программ, но реализуется схемой не менее чем квадратичной сложности в классе формул в базисе (V, Л, —>), и дизъюнктивными нормальными формами не менее чем экспоненциальной сложности

В связи с этим возникает проблема нахождения таких функций, для которых удается получить нетривиальные нижние оценки сложности в данной модели вычислений Удобным объектом для изучения сложности являются характеристические функции двоичных кодов Эти функции детально изучаются в дискретной математике, в частности, в теории кодов, исправляющих ошибки Интерес к этим функциям вызван как их структурными свойствами (одним из таких свойств является «достаточно равномерная» распределенность множества единиц значений характеристических функций этих кодов по п-мерному булеву кубу), так и широким практическим применением

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

Функция ф(п) называется сверхполиномиальной, если ее можно представить в виде ф(п) = где 1р(п) оо при п —оо

Ветвящиеся программы — математическая модель вычислений, хорошо моделирующая работу компьютерных программ, состоящих из условных операторов. Этот класс схем активно изучается в последнее время различными авторами Первыми работами, в которых рассматривались ветвящиеся программы, были [2, 14, 15]

Детерминированной ветвящейся программой от переменных ,хп называется ориентированный граф без циклов с одной входной вершиной и двумя выходными вершинами, одна из которых помечена нулем, другая — единицей. Из каждой вершины, за исключением выходных, выходит ровно две дуги, одна из которых помечена нулем, другая — единицей Все невыходные вершины помечены переменными из множества {жь , хп}

Под сложностью детерминированной ветвящейся программы понимается число вершин программы, помеченных переменными

Булева функция /(жь ,хп) принимает значение 1 на наборе (ах, , ап), если существует путь от входной вершины к выходной вершине, помеченной единицей, который из вершин, помеченных переменной хг, проходит по дугам, помеченных аг. Через ВР(/) обозначим сложность минимальной детерминированной ветвящейся программы, вычисляющей функцию / Любую булеву функции от п переменных можно вычислить детерминированной ветвящейся программой, сложность которой асимптотически не превосходит 2п/п

В недетерминированных программах некоторые вершины становятся непомеченными и из каждой такой вершины выходит ровно две непомеченные дуги

Булева функция / принимает значение 1 на наборе (аь ,а„), если существует путь от входной вершины к выходной вершине, помеченной единицей, который из вершин, помеченных переменной хг, проходит по дугам, помеченных аг Под сложностью недетерминированной программы понимается число вершин, помеченных переменными Через

NBP(/) обозначим сложность минимальной недетерминированной ветвящейся программы, вычисляющей функцию / Любую булеву функции от гг переменных можно вычислить недетерминированной ветвящейся программой, сложность которой не превосходит С2П/2, где С — некоторая постоянная (эта оценка следует из результата О Б Лупанова для контактно-вентильных схем [4]).

В дальнейшем под программами будут пониматься только ветвящиеся программы и поэтому слово «ветвящаяся» часто будет опускаться

Наилучшими известными нижними оценками сложности для детерминированных и недетерминированных программ, вычисляющих последовательности полностью определенных функций, являются оценки 0(n2/log2n) и 0(n3//2/ log га) соответственно Эти оценки получены в [16] с помощью метода Нечипорука Этот метод основан на мощностных соображениях и применим только к функциям специального вида, вычислимых в тех моделях, для которых сложность определяется через число элементов, помеченных переменными (контактные схемы, формулы, ветвящиеся программы и т д) Из оценки А А Разборова для контактно-вентильных схем [9] следует нижняя оценка fi(nlogloglog* п)3) для сложности недетерминированных программ, вычисляющих симметрические булевы функции, включая функцию голосования Е А Окольнишниковой [32, 34] получены нижние оценки вида Q(n log п/ log log п) сложности недетерминированных программ, вычисляющих характеристические функции кодов Рида-Маллера Такая же оценка справедлива для сложности детерминированных программ, вычисляющих некоторые симметрические булевы функции, включая функцию голосования [11], а также характеристические функции кодов

3' Пусть функция t(x) от натурального аргумента х определяется следующей рекурсией ¿(0) = 1, t(x + 1) = 2Ь№ Положим log*n = max{a;|i(x) < n}

Боуза-Чоудхури-Хоквингема [25] Кроме того, из оценки для глубины детерминированной программы [10] следует нелинейная нижняя оценка сложности детерминированных программ, вычисляющих булеву функцию, выражающую некоторое свойство пар чисел

Изучаются также ветвящиеся программы с ограничениями на структуру схем Одно из таких ограничений — ограничение на число проверок переменных в цепи, когда в любой цепи, идущей от входной вершины к выходной, вершины, помеченные любой переменной, встречаются не более к раз Такие программы называются ветвящимися ^-программами (fc-программами) Через BPk(f) и ,NBPk(f) обозначим сложность минимальных детерминированной и недетерминированной ветвящейся к программ, вычисляющих функцию /

Получены сверхполиномиальные нижние оценки сложности вычисления булевых функций детерминированными ¿-программами при к < log п/ log log п [25] и недетерминированными ¿-программами при к < log п [12]

Так как одну и ту же функцию можно вычислить ¿-программами с различными значениями к, возникает вопрос о соотношении сложностей к\- и ^-программ, вычисляющих одну и ту же булеву функцию при к\ -ф- к? В ряде работ показано, что сложности 1- и 2-программ, вычисляющих одну и ту же последовательность функций, могут отличаться в сверхполиномиальное число раз (по числу переменных булевой функции) [13, 24, 37])

В [28] конструктивно показано, что для любого натурального к, к > 2, существует последовательность булевых функций такая, что сложность недетерминированных ¿'-программ, вычисляющих функции из этой последовательности, в сверхполиномиальное число раз (по числу переменных функции) превосходит сложность недетерминированных (к In к/In 2 + Сопрограмм (где С — константа, не зависящая от к), вычисляющих ту же функцию Оценка

была получена с помощью модификации метода получения нижних оценок сложности ветвящихся /^-программ из [25] Позднее Дж Тхатхачаром [20] были приведены примеры таких последовательностей булевых функций, что сложность недетерминированных ^-программ, вычисляющих функции из этой последовательности, в сверхполиномиальное число раз (по числу переменных функции) превосходит сложность недетерминированных (к + 1)-программ, вычисляющих ту же функцию (оценка была получена с помощью метода из [12])

Автором диссертации [25, 32] предложен метод, позволяющий сводить получение нижних оценок сложности программ без ограничений на структуры, вычисляющих булевы функции, к получению нижних оценок сложности /с-программ, вычисляющих подфункции рассматриваемой функции Применение этого метода позволило получить нелинейные нижние оценки сложности недетерминированных программ, вычисляющих характеристические функции кодов Рида-Маллера Схемы с ограничениями рассматривались в работах многих авторов Сверхполиномиальные нижние оценки для схем из функциональных элементов в монотонном базисе были получены А А Разборовым [8] и А А Андреевым [1] Кроме того, С В Кузнецов, Е А. Окольнишникова, А К Пулатов, Г А Ткачев и др получили сверхполиномиальные нижние оценки для схем с различными ограничениями на структуру Тем не менее, метод, изложенный в диссертации, является, видимо, первым методом, с помощью которого удалось получить нетривиальные нижние оценки для схем без ограничений, существенно используя нижние оценки сложности схем с ограничениями

С рассмотрением факторов, влияющих на сложность вычисления булевых функций, связано рассмотрение операций над булевыми функциями, которые позволяют из просто вычислимых функций получать сложно вычислимые, в том числе и в классе программ В [6, 7] было показано, что операция геометрического проектирования множества единиц

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

В [30] была введена операция монотонного расширения булевой функции Монотонное расширение булевой функции / — это монотонная булева функция с минимальным,числом единиц, являющаяся расширением функции / В диссертации показано, что операция монотонного расширения булевых функций может приводить к существенному усложнению функции, и построены примеры последовательностей функций, сложность вычисления которых контактными схемами, формулами в любом конечном базисе, ветвящимися программы существенно меньше сложности вычисления монотонного расширения этих функций

Научная новизна. Все основные результаты диссертации являются новыми Укажем наиболее важные из них

—• В диссертации предложен метод получения сверхполиномиальных нижних оценок сложности ^-программ С его помощью получена сверхполиномиальная нижняя оценка сложности ветвящихся /¡-программ, вычисляющих характеристические функции кодов Боуза-Чоудхури-Хоквингема (БЧХ-коды)

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

сверхполиномиальная нижняя оценка сложности вычисления характеристической функции свойства гиперграфов не содержать изолированных вершин Показано, что для любого натурального к, к > 2, существует последовательность булевых функций такая, что сложность недетерминированных ^-программ в сверхполиномиальное (по числу переменных булевой функции) число раз превосходит сложность [ЫпА;/1п2 + С]-программ (С — константа, не зависящая от к), вычисляющих функции из этой последовательности

— Предложен метод получения нелинейных нижних оценок сложности детерминированных и недетерминированных программ, вычисляющих булевы функции С его помощью получена оценка П(пк^п/к^к^п) для сложности детерминированных и недетерминированных программ, вычисляющих характеристические функции кодов Рида-Маллера и БЧХ-кодов (при некоторых значениях параметров этих кодов)

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

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

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

Апробация. Результаты работы докладывались на следующих научных конференциях и семинарах конференции «Проблемы теоретической кибернетики» (Иркутск, 1986, Горький, 1988, Нижний Новгород, 1999, Казань, 2002, Пенза, 2005), III конференция по прикладной логике (Новосибирск,

1992), V Международная конференция «Дискретные модели в теории управляющих систем» (Ратмино, 2003), III Международном симпозиуме «Stochactic algorithms foundations and applications» (SAGA 2005) (Москва, 2005), Российская конференция «Дискретный анализ и исследование операций» (Новосибирск, 2002, 2004), 11-ый Международный симпозиум ее приложения» (Москва, 1993, 2004), Всесоюзные и Международные школы-семинары «Синтез и сложность управляющих систем» (Львов, 1988, Нижний Новгород, 1998, Нижний Новгород, 2000, Пенза, 2001, Нижний Новгород, 2003, Новосибирск, 2004), школа-семинар «Сложность булевых функций» (Казань, 1999), V Сибирская научная школа-семинар «Компьютерная безопасность и криптография» SIBERCRYPT'06 (Шушенское, 2006), в Международном математическом центре им С. Банаха (Варшава, 1991), на семинарах «Complexity of Boolean functions» (Dagstuhl, 1999, 2001), в МГУ на семинаре «Математические вопросы кибернетики» (руководитель О Б Лупанов), на семинаре «Дискретный анализ» Института математики им С Л Соболева СО РАН (руководители А А Евдокимов и А Д Коршунов)

Публикации. По теме диссертации опубликовано 28 работ, список которых приведен в конце автореферата

Структура диссертации. Диссертация состоит из введения, пяти глав, и списка литературы, содержащего 123 наименований Полный объем диссертации — 185 страниц

СОДЕРЖАНИЕ РАБОТЫ

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

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

сложности вычисления булевых функций ^-программами для значений к, не превышающих 0(logn/ log log и)

Идея метода состоит в следующем Пусть V — программа, вычисляющая булеву функцию / от N переменных Если /(аь ,,ajv) = 1, то в Я существует хотя бы один путь от входной вершины к выходной вершине, помеченной единицей, в котором каждая дута, выходящая из вершины, помеченной переменной жг, помечена символом а,. Поставим в соответствие набору (ai, ., а^) один из таких путей На, этом пути выбирается некоторое подмножество вершин Мощности выбранных подмножеств зависят только от заранее выбранных параметров и существенно меньше, чем длина пути С каждым таким подмножеством вершин ассоциируется функция /г, зависящая только от этого подмножества вершин программы V При этом / = У/г Если число единиц каждой функции /г не очень большое, а число единиц функции / велико, то число различных подмножеств вершин, которые ставятся в соответствие единицам булевой функции, велико Это позволяет оценить снизу мощности множества вершин программы С помощью этого метода были получены сверхполиномиальные нижние оценки сложности ¿¡-программ, вычисляющих характеристические функции Б^Х-ксдов

Рассматриваются всевозможные представления функции /(У), |rj = п, в виде

fvo - V л1^;1 и л /даи

где Yj, Yf и У?° — непересекающиеся множества, Y — Y^ U У/ U У/, (У| = n, > mi, |У/| > m2, |У/| = п ~ |У/| - |У/|

Минимальное число дизъюнктивных членов в этом представлении обозначается через A(f,n,mi,mz) Это число зависит только от рассматриваемой функции и от выбранных значений параметров гщ и т2 Доказана теорема 2 2

позволяющая оценить снизу сложность ¿-программ, вычисляющих булевы функции, используя величину А(/, п, т^. т^) Частным случаем этой теоремы при конкретных значения тх и То2 является оценка сложности ¿-программы, вычисляющей булеву функцию /, существенно зависящую от п переменных

№РкЦ) >тах|(А(/,п,т1,т2))1/{4к)\

( 1

где гпх

пI (2(ке)к) , тп2 = \п/(к + 1)] (следствие 2 1)

Можно предложить несколько способов получения нижней оценки для величины А(/, п, ггц, т2) [25, 26] В диссертации используется следующая оценка Среди всех г-мерных граней булева куба размерности п выделяется грань, в которой содержится максимальное число единиц функции / Число единиц в такой грани обозначим через Нг(/) В лемме 2 5 показано, что величина А(/, п, тл^т^) удовлетворяет неравенству

Аи,п,т1,т2)> 1/1(1)1

2 ™#т1(/)Ят2(/)

Это позволяет получать нижние оценки сложности ¿-программ, используя величину Нг(/) (теорема 2.4) Частным случаем этой теоремы при конкретных значениях т\ и т,2 является нижняя оценка сложности ¿-программ, вычисляющих булеву функцию /, существенно зависящую от и переменных,

ЫВРЛ(/) > тах<(п, * ' I/ Ч1)!

^ 8 у/к \2п-т1-т2Нт1(/)Нт2 где т! = "

пI (2(¿е)*) , т2 = [п/(А; + 1)] (следствие 2 3)

Используя эти результаты, были получены сверхполиномиальные нижние оценки сложности ¿-программ, вычисляющих характеристические функций БЧХ-кодов В2г+1

при некоторых значениях параметров кодов А именно, было показано (теорема 2 5), что при к = [С 1п п/ 1п 1п п\, где 0 < С < 1 — константа, существуют БЧХ-коды

ехр (^„¡пп In In In n + О ), которые можно вычислить

только ¿-программами, сложность которых не меньше чем ехр(п^~с^2) В то же время существуют детерминированные программы сложности не более гг.2, которые вычисляют характеристические функции таких кодов (лемма 2 7)

Прямое применение метода главы 2 не всегда позволяет получать высокие нижние оценки сложности ¿-программ, вычисляющих булевы функции В главе 3 предложена модификация метода, позволяющая получать сверхполиномиальные нижние оценки сложности ¿-программ, вычисляющих функции от переменных, соответствующих ребрам графов, гиперграфов и иных объектов, имеющих многомерную природу Вводится булева функция Fn>s от N — (") булевых переменных, соответствующих ребрам гиперграфа, получена высокая нижняя оценка сложности ¿-программ, вычисляющих функцию FnyS (теорема 3 2). А именно, показано, что при к(п) < С\ Inn/ In Inn, где С\ < 1/2 — константа, сложность недетерминированной ¿-программы, вычисляющей функцию FHiS, при некоторых значениях параметров не меньше чем ехр (3n1_2Cl) (следствие 3 3)

С помощью функции FnjS показывается, что для любого натурального ¿, ¿ > 2, существует последовательность булевых функций такая, что сложность недетерминированных ¿-программ, вычисляющих каждую функцию из этой последовательности, в сверхполиномиальное число раз (по числу переменных булевой функции) превосходит сложность недетерминированных [¿In¿/In2 + С]-программ (где С — константа, не зависящая от к), вычисляющих ту же функцию (теорема 3 3).

В главе 4 диссертации предложен метод получения

с параметрами

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

Идея этого метода состоит в следующем Пусть V — произвольная программа, вычисляющая булеву функцию /(Х1,Х2, ,хп) Если для какой-то переменной хг число проверок по этой переменной в некоторой цепи (пути) от входной вершины к выходной превышает к{п), где >к(п) —>• оо при п —> оо, и число таких переменных не очень мало, то сложность программы V не может быть малой Если число таких переменных мало, то эти переменные можно «забить» константами, что позволит от первоначальной схемы V перейти к схеме V с ограничениями на число проверок каждой переменной в цепи, т е рассмотреть вычисление некоторой подфункции функции / ветвящейся к (п)-программой При этом для получения нижних оценок сложности к-программ, вычисляющих подфункции булевой функции, можно использовать как подход, предложенный в главах 2, 3 диссертации, так и подход А Бородина, А. Разборова и Р Смоленского [12, 20]

Совместное применение теоремы 4 1 и теоремы 2 2 позволяет получать нелинейные нижние оценки сложности ветвящихся программ, вычисляющих булевы функции, исходя из сложности покрытий множества единиц булевой функции функциями определенного вида (теоремы 4 2, 4 3 и 4 4) или исходя из числа единиц булевой функции в гранях определенной размерности (теоремы 4 5, 4 б и 4 7) В частности, в теореме 4 б утверждается, что сложность ИВР(дп) любой недетерминированной программы (без ограничений),

вычисляющей функцию дп(Хп), удовлетворяет неравенству ШР(дп)

> mm {<**(„), ^ • 1/<4"} ,

где А;(п) — растущая функция, С — константа, т,) = \\{1~С)п\/{2{ке)к)}, т2 = |"Г(1 - С)п\Цк + 1)] Таким образом, для того чтобы использовать эту теорему для получения нетривиальных нижних оценок сложности, нужно иметь как «хорошую» нижнюю оценку числа единиц функции, так и «хорошую» верхнюю оценку числа единиц в подкубах размерности mi и тг

Применение теорем 4 5, 4 6 и 4 7 позволило получить нижние оценки сложности недетерминированных программ, вычисляющих характеристические функции кодов Рида-Мал-лера 7Z(u,m) для широкого спектра параметров этих кодов (теоремы 4 10, 4 12) Для получения верхней оценки числа единиц кода Рида-Маллера в подкубах размерности % используются результаты по обобщенным весам Хемминга из [23]. Приведена верхняя оценка сложности недетерминированных программ, вычисляющих характеристические функции кодов Рида-Маллера (теорема 4 13) Показано, что для сложности NBP(7Z(um,m)) вычисления характеристической функции кода lZ(um-c0,m), где С0 > 3 — константа, имеет место оценка

п log п/ log log n ^ NBP(7^(ttTO_c;0,m)) < nlog00'1 п,

где п — число переменных функции 7£(ит_с0, то)

Показано, что существуют булевы функции, для которых применение теоремы 41 диссертации и подхода из [25, 32] для получения нижних оценок сложности А;-программ дает лучшие оценки сложности программ без ограничений, вычисляющих эти функции, чем применение теоремы 4 1 и подхода А Бородина, А А Разборова. Р Смоленского [12, 20]

И наоборот, известны примеры булевых функций, для которых имеет место обратное соотношение, а именно применение теоремы 4 1 и подхода А Бородина, А А Разборова, Р Смоленского [12, 20] дает лучшие нижние оценки сложности программ без ограничений, вычисляющих эти функции, чем совместное использование теоремы 4 1 и подхода из [25, 32] (следствие 4 2)

Получены нижние оценки сложности программ, вычисляющих характеристические функции кодов с большим числом вершин (включая коды Боуза-Чоудхури-Хоквингема) (теорема 4 14 и следствие 4 5) При этом полученные нижние оценки 0(?г1пп/ 1п1пп)) при некоторых значениях параметров кодов оказываются близки к верхним оценкам (следствие 4 4) В главе 5 рассматриваются понятия геометрической проекции и монотонного расширения булевых функций

Введем понятие геометрической проекции Проекцию булевой функции /(жь ,хп) по переменным хп, ,хч будем обозначать через Р/Жн, Лл(х31, ,хи__к), где {]и =

{1,2, , п} \ {гх,. ,гй}. Без ограничения общности можно считать, что г* = I для 1 = 1, ,к По определению положим

рЛя, ,хк(хк+ъ ,хп)= /(о"1, ,ак,хк+1, ,хп),

где аг Е {0,1} при г ~ 1, , к

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

и недетерминированных ^-программ при к > 2 (теорема 5 1) Достаточно высокие нижние оценки сложности для схем, вычисляющих проекции рассматриваемых функций, получены методом Нечипорука Вместе с тем сама исходная функция вычисляется достаточно просто В классе недетерминированных 1-программ сложность вычисления проекции булевой функции не превышает сложности вычисления самой функции (теорема 5 2)

Кроме того, показано, что если для некоторой булевой функции / существует «большой» разрыв (более чем квадратичный относительно сложности NBP(/)) между сложностью детерминированных и недетерминированных программ, вычисляющих эту функцию, то можно построить пример такой функции, что существует «большой» разрыв между сложностью детерминированных программ, вычисляющих эту функцию, и сложностью программ, вычисляющих ее проекцию (теорема 5.3)

Будем говорить, что булева функция д(хг, ,хк) является монотонным расширением функции /(жъ ,хк), если д(в\, , (Зк) = 1 тогда и только тогда, когда существует такой набор (аи ,ак), что {аъ. ,ак) г< (А, -,Рк) и /(«!, . ,ак) = 1 (Здесь, как обычно, (а?!, ,ак) ^ (Л> , рк) означает, что ол < /Зь . ,ак < ¡Зк) Таким образом, монотонное расширение булевой функции / — это монотонная булева функция с минимальным числом единиц, среди которых содержатся единицы функции /

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

этой функции В главе 5 строится пример последовательности таких булевых функций, что монотонное расширение каждой функции вычисляется существенно сложнее самой функции в классе формул над конечным базисом, в классе контактных схем, в классе детерминированных и недетерминированных программ, а также детерминированных и недетерминированных ¿-программ при к > 2 (теорема 5 4) Достаточно высокие нижние оценки сложности для схем, вычисляющих монотонное расширение рассматриваемых функций, получены методом Нечипорука Вместе с тем сами исходные функции вычисляются достаточно просто

В теореме 5 б указывается некоторая связь между операцией геометрического проектирования и операцией монотонного расширения А именно, предложен алгоритм, позволяющий по произвольной булевой функции /(X) от п переменных построить функцию д(Х, У) от 2п переменных такую, что

1) сложность ее вычисления незначительно отличается от сложности вычисления /(X) в основных моделях вычислений,

2) проекция д(Х,У) по переменным из У совпадает с монотонным расширением функции /(X)

В заключение автор выражает глубокую признательность зав лабораторией дискретного анализа А А Евдокимову, д ф -м н А Д Коршунову и к ф -м н Ю Л Васильеву за ряд ценных советов и замечаний при написании данной диссертации

ЛИТЕРАТУРА

[1] Андреев А. Е. Об одном методе получения нижних оценок сложности индивидуальных монотонных функций // Докл АН СССР - 1985 - Т 282, № 5 - С 1033-1037

[2] Кузьмин В. А. Оценка сложности реализации функций алгебры логики простейшими видами бинарных программ

// Методы дискретного анализа в теории кодов и схем Сб научн тр — Вып 29 — Новосибирск Ин-т математики СО АН СССР, 1976 - С 11-39

[3] Колмогоров А. Н. Три подхода к определению понятия "количество информации"// Проблемы передачи информации — 1965 — Т I, вып 1 — С 3-11

[4] Jlyпанов О. Б. О вентильных и контактно-вентильных схемах // Докл АН СССР - 1956 - Т 111, № 6 -С 1171-1174

[5] Лупанов О. Б. О синтезе некоторых классов управляющих систем // Проблемы кибернетики Вып 10 — М Физматгиз, 1963 - С 63-97

[6] Окольнишникова Е. А. О сравнении сложностей реализации булевых функций и их проекций // Методы дискретного анализа в теории управляющих систем Сб науч тр — Вып 31 — Новосибирск Ин-т математики СО АН СССР, 1977 - С 76-80

[7] Пулатов А. К. О влиянии нулевых цепей на сложность реализации булевых функций контактными схемами // Методы дискретного анализа в решении комбинаторных задач Сб науч тр — Вып 30 — Новосибирск Ин-т математики СО АН СССР - 1977 - С. 30-37

[8] Разборов А. А. Нижние оценки сложности монотонной сложности некоторых булевых функций // Докл АН СССР - 1985 - Т 281, № 4 — С 798-801

[9] Разборов А. А. Нижние оценки сложности реализации симметрических булевых функций контактно-вентильными схемами // Мат заметки — 1990 — Т 48, вып 6 - С 79-90

[10] Ajtai M. A поп-lmear time lower bound for boolean branching programs // Proc of the 40th Annual Symposium on Foundations of Computer Science, FOCS '99 (New York, October 17-19, 1999) — Los Alamitos IEEE Computer Society, 1999 - P 60-70

[11] Babai L., Pudlak P., Rodl V., and Szemeredi M. Lower bounds to the complexity of symmetric Boolean functions // Theoret Comput Sci — 1990 - V 74, N 3 - P 313-324

[12] Borodin A., Razborov A., Smolensky R. On

lower bounds for read-fc-times branching programs // Computational Complexity — 1993. — V 3, N 1 — P 1-18

[13] Dunne P. E. Lower bounds on the complexity of 1-time only branching programs (preliminary version) // Fundamentals of Computation Theory, FCT'85 (Gorrbus, September 9-13, 1985) - Berlin Springer-Verl 1985 - P 90-99 (Lecture Notes in Comput Sci — V 199 )

[14] Lee C. Y. Representation of switching circuits by binary-decision programs. // Bell Syst Techn. J — 1959 — V. 38 — P 985-999 (Имеется перевод. Ли К. Представление переключательных схем с помощью программ двоичного решения // Вопросы теории математических машин — М Машиностроение, 1964 — С 219-232 )

[15] Mazek W. A fast algorithm for the syrmg editing problem and decision graph complexity lower bound on complexity of branching programs // Master's thesis Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology — Massachusetts, 1976

[16] Pudlak P. The hierarchy of Boolean circuits // Computers and Artificial Intelligence - 1987. — V 6, N 5 — P 449-468

[17] Razborov A. A. Lower bounds for deterministic and nondetermmistic branching programs // Fundamentals of Computation Theory, 8th International symposium, FCT'91 (Gosen, September 9-13, 1991). — Berlin Springer-Verlag, 1991 - P. 47-60 (Lecture Notes m Comput Sci - V 529 )

[18] Riordan J., Shannon С. E. The number on two-terminal series parallel nerworks //J Math Phys — 1942 — V 21, N2 — P 83-93 (Русский перевод- Шеннон К.Э. Работы по теории информации и кибернетике. — М . ИЛ, 1963 — С 46-58 )

[19] Shannon С. Е. The synthesis of two-termmal switching circuits // Bell Syst Techn. J - V 28, N 1. - 1949 -P 59-98 (Русский перевод Шеннон. К.Э. Работы по теории информации и кибернетике — М ИЛ, 1963 — С 59-101)

[20] Thathachar J. S. On separating the read-fc-times program hierarchy // Proc of the 30th Ann ACM Symp on Theory of Computing, STOC'98 (Dallas, May 23-26, 1998) - New York. ACM, 1999 - P. 653-662

[21] Wegener I. On the complexity of branching programs and decision trees for clique functions // Journal of the ACM — 1988 - V 35, N 2 - P 461-471

[22] Wegener I. Branching programs and binary decision diagrams. Theory and applications. — Philadelphia, PA SI AM, 2000 - 408 pp

[23] Wei V. K. Generalized Hamming weights for linear codes // IEEE Trans on Inform Theory - 1991 - V 37, N 5 -P 1412-1418.

[24] Zak S. An exponential lower bound for one-time-only branching programs // Proc of the 11th Int Symp on

Mathematical Foundations of Computer Science, MFCS'84 (Praha, September 3-7, 1984) — Berlin Sprmger-Verlag, 1984. — P 562-566 ( Lecture Notes in Comput Sei — V 176)

СТАТЬИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

[25] Окольнишникова Е. А. Нижние оценки сложности реализации характеристических функций двоичных кодов бинарными программами // Методы дискретного анализа в синтезе реализаций булевых функций Сб науч тр. -Вып 51 — Новосибирск Ин-т математики СО АН СССР, 1991.-С 61-83

[26] Okol'nishnikova Е. A. Lower bounds on branching programs // Siberian Adv Math — 1993 — V 3, N 1 -P 152-166

[27] Окольнишникова E. А. О сравнении сложностей бинарных /с-программ // Дискрет анализ и иссдед операций — 1995 - Т 2, № 4 - С 54-73 (Перевод статьи Okol'nishnikova Е. A. On Comparison between the sizes of read-fc-times branching programs // Operation Research and Discrete Analysis (ed A D Korshunov) (Series Mathematics and Its Applications). — Dordrecht Kluwer Academic Publishers, 1997. — P 205-225 )

[28] Okol'nishnikova E. A. On the hierarchy of nondetermimstic branching ^-programs // Fundamentals of computation theory. 11th International symposium, FCT 97 (Krakov, September 1-3, 1997) — Berlin Springer, 1997 — P 376-387. (Lecture Notes m Comput. Sei - V 1279 )

[29] Окольнишникова E. А. О сравнении сложностей недетерминированных ветвящихся ^-программ // Дискрет анализ и исслед операций Серия 1 — 1999 — Т 6, № 1 — С 65-85. (Перевод статьи Okol'nishnikova Е. А.

Comparing the sizes of nondetermimstic branching read-k-times programs // Discrete Applied Mathematics — 2004 — V 135 — P 205-222 )

|30j Окольнишникова E. А. О двух операциях над булевыми функциями // Дискрет анализ и исслед операций Сер 1 - 2000 - Т 7, № 1. — С 79-93

[31] Окольнишникова Е. А. О сложности ветвящихся программ // Дискретная математика и ее приложения Сб лекций молодежных научных школ по дискретной математике и ее приложениям, II. — М Изд-во центра приклад исслед при мех.-мат фак-те МГУ, 2001 — С 41-58

[32] Окольнишникова Е. А. Об одном методе получения нижних оценок сложности реализации булевых функций недетерминированными ветвящимися программами // Дискрет анализ и исслед операций Сер 1 — 2001 — Т 8, № 4 - С 76-112

[33] Окольнишникова Е. А. Сложность ветвящихся программ // Математические вопросы кибернетики Вып. 10 — М Физматлит, 2001 - С 69-82

[34] Окольнишникова Е. А. О сложности недетерминированных ветвящихся программ, реализующих характеристические функции кодов Рида-Маллера // Дискрет анализ и исслед операций Сер 1 — 2003 Т 10, № 3 С 67-81

[35] Okol'nishnikova Е. A. On some bounds on the size of branching programs (a survey) // Stochastic Algorithms, Foundations and Application 3rd International symposium, SAGA 2005 (Moscow, October 20-22, 2005) - Berlin. Springer, 2005 — P 107-115 (Lecture Notes m Comput Sci -V 3777 )

[36] Окольнишникова Е. А. Нижние оценки сложности ветвящихся программ / / Вестник Томского гос университета Приложение — 2006 — № 17 — С 42-46

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

[37] Окольнишникова Е. А. Об одном соотношении сложностей булевых функций / / Проблемы теоретической кибернетики VIII Всесоюз науч. конф (Горький, июль 1988 г) Тез докл — Горький' Горьковский гос пед. институт, 1988 — С 63

[38] Окольнишникова Е. А. Нижние оценки сложности реализации булевых функций бинарными программами // Логика и семантическое программирование (Вычислительные системы). Сб, научн тр. — Вып 146 — Новосибирск- Йн-т математики СО АН СССР, 1992 — С 177-180

[39] Окольнишникова Е. А. О нижних оценках сложности для бинарных программ // Сб трудов IV Межгос семинара по дискретной математике и ее приложениям (Москва, 2-4 февраля 1993 г). — M Изд-во мех-мат фак-та МГУ, 1993. - С. 79.

[40] Окольнишникова Е. А. Об одном соотношении сложностей бинарных fc-программ // Дискрет анализ и исслед операций (Тез докл VI Межгос школа-семинар "Синтез и сложность управляющих систем" Нижний Новгород, 21-24 ноября 1994 г) - 1995 - Т. 2, № 1 - С 77-78

[41] Окольнишникова Е. А. Об одном соотношении сложностей бинарных программ // Проблемы теоретической кибернетики XI Междунар конф (Ульяновск, 10-14 июня 1996 г) Тез докл — Москва Изд центр РГГУ, 1996 - С 153-154

[42] Окольнишникова Е. А. Об иерархии бинарных к-программ // II Сибирский Конгресс по Прикладной и Индустриальной Математике, ИНПРИМ-96 (Новосибирск, 27-31 мая 1996) Тез докл — Новосибирск Изд-во Института математики СО РАН, 1996 — С. 122

[43] Окольнишникова Е. А. О сложности ветвящихся программ // Материалы IX Межгосударственной школы-семинара "Синтез и сложность управляющих систем" (Нижний Новгород, 16-19 декабря 1998) — М Изд-во мех-мат фак-та МГУ, 1999 - С 63-70

[44] Окольнишникова Е. А. О сложности реализации проекций булевых функций ветвящимися программами // Проблемы теоретической кибернетики XII Междунар конф (Нижний Новгород, 17-22 мая 1999) Тез докл — М Изд-во Изд-во мех-мат фак-та МГУ, 1999 — Часть 2 -С 178

[45] Окольнишникова Е. А. О двух операциях над булевыми функциями // Материалы XI Международной школы-семинара "Синтез и сложность управляющих систем"(Нижний Новгород, 20-25 ноября 2000 г) — М Изд-во центра прикл исслед при мех -мат фак-те МГУ, 2001 - Часть II - С 126-134

[46] Окольнишникова Е. А. Нижние оценки сложности ветвящихся программ // Материалы XII Межгосударственной школы-семинара "Синтез и сложность управляющих систем"(Пенза, 19-21 октября 2001 г.) — М Изд-во центра приклад исслед при мех -мат фак-те МГУ, 2001 -Часть II - С 160-164

[47] Окольнишникова Е. А. Оценки сложности вычисления булевых функций ветвящимися программами / / Российская конф "Дискретный анализ и исследование

операций"(Новосибирск, 24-28 июня 2002 г) Материалы конференции. — Новосибирск* Изд-во Ин-та математики, 2002 - С 88-93

[48] Окольнишникова Е. А. О сравнении двух методов получения нижних оценок сложности ветвящихся ¿-программ // Проблемы теоретической кибернетики Тезисы докладов XIII Международной конф. (Казань, 27-31 мая 2002 г) — М Изд-во центра прикл исслед при мех -мат фак-те МГУ, 2002 - Часть II - С 135

[49] Окольнишникова Е. А. О сложности характеристических функций кодов Рида-Маллера // Материалы XIV Международной школы-семинара "Синтез и сложность управляющих систем" (Нижний Новгород, 27 октября - 1 ноября 2003 г) — Нижний Новгород Изд-во Нижегородского гос. лед университета, 2003 — С 60-64

[50] Окольнишникова Е. А. О сложности ветвящихся программ // Материалы VIII Международного семинара "Дискретная математика и ее приложения"(Москва, 2-6 февраля 2004 г) — М . Изд-во мех -мат фак-та МГУ, 2004. - С 85-86

[51] Окольнишникова Е. А. О некоторых комбинаторных задачах, возникающих в теории сложности // Материалы XV Международной школы-семинара "Синтез и сложность управляющих систем" (Новосибирск, 18 - 23 октября 2004 г). — Новосибирск Изд-во ИМ СО РАН, 2004 - С 57-61

[52] Okol'nishnikova Е. A. On some operations over Boolean functions // Proc. of the seminar "The complexity of Boolean functions"(Dagstuhl, 31 октября - 5 ноября 1999 г) — Germany, Dagstuhl, 1999. - P 10

Подписано в печать 06 09 2007г Формат бумаги 60x84 1\16 Объем 1,75 печ л Тираж 130 экз_Заказ № 130_

Отпечатано в ООО « Омега Принт» 630090, г Новосибирск, пр Ак Лаврентьева,6

Введение

Глава 1. Обзор результатов по сложности ветвящихся программ.

§ 1.1. Определения, предварительные сведения

1.1.1. Контактно-вентильные схемы

1.1.2. Ориентированные контактно-вентильные схемы

1.1.3. Ациклические контактно-вентильные схемы

1.1.4. Недетерминированные ветвящиеся программы

1.1.5. Детерминированные ветвящиеся программы.

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

§ 1.2. Нижние оценки сложности для недетерминированных ветвящихся программ

1.2.1. Оценка Э. И. Нечипорука

1.2.2. Оценки для симметрических булевых функций

1.2.3. Оценки для характеристических функций двоичных кодов

§ 1.3. Нижние оценки сложности для детерминированных ветвящихся программ

1.3.1. Оценка Э. И. Нечипорука

1.3.2. Оценки для симметрических булевых функций

1.3.3. Оценки для характеристических функций двоичных кодов

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

§ 1.4. Ветвящиеся программы ограниченной ширины

§ 1.5. Ветвящиеся программы ограниченной глубины

§ 1.6. Ветвящиеся /¿-программы

1.6.1. Нижние оценки сложности для ветвящихся 1-программ.

1.6.2. Нижние оценки сложности для ветвящихся /¿-программ.

1.6.3. Иерархия ветвящихся /¿-программ.

1.6.4. Нижние оценки для схем без ограничений

1.6.5. Упорядоченные бинарные деревья решений

Глава 2. Метод получения нижних оценок сложности ветвящихся /¿-программ

§ 2.1. Идея метода получения нижних оценок сложности ветвящихся /¿-программ

§ 2.2. Определения и предварительные сведения.

§ 2.3. Установление соответствия между множеством единиц булевой функции и подмножествами вершин ветвящейся /¿-программы

§ 2.4. Нижние оценки сложности ветвящихся /¿-программ

§ 2.5. Нижние оценки сложности вычисления характеристических функций БЧХ-кодов ветвящимися

-программами

Глава 3. Модификация метода получения нижних оценок сложности ветвящихся /¿-программ. Сравнение сложностей ветвящихся /¿-программ

§ 3.1. Определение и свойства функции Рп

§ 3.2. Построение последовательности

§ 3.3. Оценка мощности множества

§ 3.4. Сравнение сложностей реализации булевых функций

Глава 4. Нижние оценки сложности ветвящихся программ

§ 4.1. Сведение нижних оценок сложности для программ без ограничений к оценкам сложности для fc-программ

§ 4.2. Нижние оценки сложности ветвящихся программ без ограничений

§ 4.3. Нижние оценки сложности вычисления характеристических функций кодов Рида-Маллера

4.3.1. Подсчет числа единиц в подкубах для кодов Рида-Маллера

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

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

4.3.4. Нижние оценки сложности вычисления характеристических функций кодов Рида-Маллера

§ 4.4. Нижние оценки сложности вычисления характеристических функций двоичных кодов с большим числом кодовых вершин

Глава 5. О некоторых операциях над булевыми функциями.

§ 5.1. Геометрическая проекция

§ 5.2. Монотонное расширение

Теория сложности вычислений является важным разделом математической кибернетики. Целью теории является оценивание величины ресурсов, необходимых для решения тех или иных вычислительных задач. Рассматриваются различные модели вычисления такие, например, как машины Тьюринга, автоматы, нормальные алгоритмы, схемы из функциональных элементов, формулы в различных базисах и т. д.1) В качестве оцениваемых ресурсов рассматриваются время вычисления, объем используемой памяти, длина программы и др. Под сложностью вычисления понимается величина этого ресурса. При этом сложность зависит как от модели вычислений, так и от выбранного оцениваемого ресурса. Основным объектом теории является получение верхних и нижних оценок сложности. При этом получение нижних оценок сложности в большинстве рассматриваемых моделях вычислений представляет наибольшую трудность. Это объясняется тем, что при установлении нижних оценок сложности надо в той или иной мере просмотреть все возможные способы вычисления рассматриваемого объекта и показать, что вычислить этот объект с меньшими затратами невозможно. При получении нижних оценок сложности возникают, решаются и используются важные и интересные задачи из различных областей дискретной математики.

Известно [14, 15, 16, 104, 111], что во многих моделях вычисления, таких как схемы из функциональных элементов, контактные схемы, Важным понятием в теории сложности является также сложность объектов по Колмогорову, введенная в (10] для алгоритмического определения понятия количества информации. формулы в конечных базисах, ветвящиеся программы, почти все булевы функции вычисляются очень сложно (экспонента от числа переменных функции), тем не менее, лишь для небольшого числа полностью определенных булевых функций доказано, что их нельзя вычислить с линейной сложностью (для схем из функциональных элементов удалось получить лишь линейные оценки) относительно числа переменных булевой функции. К этому направлению относятся работы А. А. Разборова [54] и А. Е. Андреева [2], в которых были получены сверхполиномиальные2) нижние оценки сложности для схем из функциональных элементов в монотонном базисе, реализующих известные функции.

Сложность вычисления булевой функции зависит от модели вычисления. Так, например, линейная булева функция вычисляется с линейной сложностью в классе схем из функциональных элементов, контактных схем, ветвящихся программ, но реализуется схемой не менее чем квадратичной сложности в классе формул в базисе (V, Л, —|), и дизъюнктивными нормальными формами не менее чем экспоненциальной сложности.

В связи с этим возникает проблема нахождения таких функций, для которых удается получить нетривиальные нижние оценки сложности в данной модели вычислений. Удобным объектом для изучения сложности являются характеристические функции двоичных кодов. Эти функции детально изучаются в дискретной математике, в частности, в теории кодов, исправляющих ошибки. Интерес к этим функциям вызван как их структурными свойствами (одним из таких свойств является «достаточно равномерная» распределенность множества единиц значений

2)функция ф(п) называется сверхполиномиальной, если ее можно представить в виде ф(п) = пФСп)> Где ф(п) —> оо при п оо. характеристических функций этих кодов по п-мерному булеву кубу), так и широким практическим применением.

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

Ветвящиеся программы — математическая модель вычислений, хорошо моделирующая работу компьютерных программ, состоящих из условных операторов. Этот класс схем активно изучается в последнее время различными авторами. Первыми работами, в которых рассматривались ветвящиеся программы, были [14, 94, 95].

Детерминированной ветвящейся программой от переменных хг,. ,хп называется ориентированный граф без циклов с одной входной вершиной и двумя выходными вершинами, одна из которых помечена нулем, другая — единицей. Из каждой вершины, за исключением выходных, выходит ровно две дуги, одна из которых помечена нулем, другая — единицей. Все невыходные вершины помечены переменными из множества {жх,. ,хп}.

Под сложностью детерминированной ветвящейся программы понимается число вершин программы, помеченных переменными.

Булева функция . ,хп) принимает значение 1 на наборе ах,., ап): если существует путь от входной вершины к выходной вершине, помеченной единицей, который из вершин, помеченных переменной х^, проходит по дугам, помеченных щ. Через ВР(/) обозначим сложность минимальной детерминированной ветвящейся программы, вычисляющей функцию /. Любую булеву функции от п переменных можно вычислить детерминированной ветвящейся программой, сложность которой асимптотически не превосходит 2п/п.

В недетерминированных программах некоторые вершины становятся непомеченными и из каждой такой вершины выходит ровно две непомеченные дуги.

Булева функция / принимает значение 1 на наборе (а\,., ап), если существует путь от входной вершины к выходной вершине, помеченной единицей, который из вершин, помеченных переменной Xi, проходит по дугам, помеченных щ. Под сложностью недетерминированной программы понимается число вершин, помеченных переменными. Через NBP(/) обозначим сложность минимальной недетерминированной ветвящейся программы, вычисляющей функцию /. Любую булеву функции от п переменных можно вычислить недетерминированной ветвящейся программой, сложность которой не превосходит С2п/2. где С — некоторая постоянная (эта оценка следует из результата О. Б. Лупанова для контактно-вентильных схем [15]).

В дальнейшем под программами будут пониматься только ветвящиеся программы и поэтому слово «ветвящаяся» часто будет опускаться.

Наилучшими известными нижними оценками сложности для детерминированных и недетерминированных программ, вычисляющих последовательности полностью определенных функций, являются оценки Q,(n2/ log2 п) и il(n3/2/logn) соответственно. Эти оценки получены в [101] с помощью метода Нечипорука. Этот метод основан на мощностных соображениях и применим только к функциям специального вида, вычислимых в тех моделях, для которых сложность определяется через число элементов, помеченных переменными (контактные схемы, формулы, ветвящиеся программы и т. д.). Из оценки А. А. Раз-борова для контактно-вентильных схем [55] следует нижняя оценка

Q(n log log log* n)3j для сложности недетерминированных программ, вычисляющих симметрические булевы функции, включая функцию голосования. Б. А. Окольнишниковой [39, 46] получены нижние оценки вида i2(nlogn/ log log п) сложности недетерминированных программ, вычисляющих характеристические функции кодов Рида-Маллера. Такая же оценка справедлива для сложности детерминированных программ, вычисляющих некоторые симметрические булевы функции, включая функцию голосования [70], а также характеристические функции кодов Боуза-Чоудхури-Хоквингема [27]. Кроме того, из оценки для глубины детерминированной программы [66] следует нелинейная нижняя оценка сложности детерминированных программ, вычисляющих булеву функцию, выражающую некоторое свойство пар чисел.

Изучаются также ветвящиеся программы с ограничениями на структуру схем. Одно из таких ограничений — ограничение на число проверок переменных в цепи, когда в любой цепи, идущей от входной вершины к выходной, вершины, помеченные любой переменной, встречаются не более к раз. Такие программы называются ветвящимися /¿-программами (/¿-программами). Через ВРА;(/) и NBPk(f) обозначим сложность минимальных детерминированной и недетерминированной ветвящейся к программ, вычисляющих функцию /.

Получены сверхполиномиальные нижние оценки сложности вычисления булевых функций детерминированными /¿-программами при к < log п] log log п [27] и недетерминированными /¿-программами при к < logn [83].

Так как одну и ту же функцию можно вычислить /¿-программами с различными значениями к, возникает вопрос о соотношении сложностей

3) Пусть функция t(x) or натурального аргумента ж определяется следующей рекурсией: i(0) = 1, t{x + 1) = Положим log*га = тах{х\t(x) < п}. к\- и программ, вычисляющих одну и ту же булеву функцию при к\ /с2- В ряде работ показано, что сложности 1- и 2-программ, вычисляющих одну и ту же последовательность функций, могут отличаться в сверхполиномиальное число раз (по числу переменных булевой функции) [88, 123, 26]).

В [97] конструктивно показано, что для любого натурального к, к > 2, существует последовательность булевых функций такая, что сложность недетерминированных программ. вычисляющих функции из этой последовательности, в сверхполиномиальное число раз (по числу переменных функции) превосходит сложность недетерминированных (Ып&/1п2 + Сопрограмм (где С — константа, не зависящая от к), вычисляющих ту же функцию. Оценка была получена с помощью модификации метода получения нижних оценок сложности ветвящихся /с-программ из [27]. Позднее Дж. Тхатхачаром [115] были приведены примеры таких последовательностей булевых функций, что сложность недетерминированных ^-программ, вычисляющих функции из этой последовательности, в сверхполиномиальное число раз (по числу переменных функции) превосходит сложность недетерминированных (к + 1)-программ, вычисляющих ту же функцию (оценка была получена с помощью метода из [83]).

Автором диссертации [27, 39] предложен метод, позволяющий сводить получение нижних оценок сложности программ без ограничений на структуры, вычисляющих булевы функции, к получению нижних оценок сложности ^-программ, вычисляющих подфункции рассматриваемой функции. Применение этого метода позволило получить нелинейные нижние оценки сложности недетерминированных программ, вычисляющих характеристические функции кодов Рида-Маллера. Схемы с ограничениями рассматривались в работах многих авторов.

Сверхполиномиальные нижние оценки для схем из функциональных элементов в монотонном базисе были получены А. А. Разборовым [54] и А. А. Андреевым [2]. Кроме того, C.B. Кузнецов, Е. А. Окольнишникова, А. К. Пулатов, Г. А. Ткачев и др. получили сверхполиномиальные нижние оценки для схем с различными ограничениями на структуру. Тем не менее, метод, изложенный в диссертации, является, видимо, первым методом, с помощью которого удалось получить нетривиальные нижние оценки для схем без ограничений, существенно используя нижние оценки сложности схем с ограничениями.

С рассмотрением факторов, влияющих на сложность вычисления булевых функций, связано рассмотрение операций над булевыми функциями, которые позволяют из просто вычислимых функций получать сложно вычислимые, в том числе и в классе программ. В [23, 52] было показано, что операция геометрического проектирования множества единиц булевой функции на подмножество переменных этой функции может приводить к существенному усложнению функции, и построены примеры последовательностей функций, сложность вычисления которых как контактными схемами, так и формулами в любом конечном базисе существенно меньше сложности вычисления геометрической проекции этих функций по некоторому подмножеству переменных такими же схемами. В диссертации построен аналогичный пример функции для ветвящихся программ.

В [37] была введена операция монотонного расширения булевой функции. Монотонное расширение булевой функции / — это монотонная булева функция с минимальным числом единиц, являющаяся расширением функции /. В диссертации показано, что операция монотонного расширения булевых функций может приводить к существенному усложнению функции, и построены примеры последовательностей функций, сложность вычисления которых контактными схемами, формулами в любом конечном базисе, ветвящимися программы существенно меньше сложности вычисления монотонного расширения этих функций.

Все основные результаты диссертации являются новыми. Укажем наиболее важные из них.

В диссертации предложен метод получения сверхполиномиальных нижних оценок сложности fe-программ. С его помощью получена сверхполиномиальная нижняя оценка сложности ветвящихся /¿-программ, вычисляющих характеристические функции кодов Боуза-Чоудхури-Хоквингема (БЧХ-коды)

Предложена модификация метода получения сверхполиномиальных нижних оценок сложности ветвящихся fc-программ, вычисляющих булевы функции, которая (модификация) позволяет получать сверхполиномиальные нижние оценки сложности для функций, заданных на переменных, соответствующих ребрам графов, гиперграфов и иных объектах, имеющих многомерную природу. Получена сверхполиномиальная нижняя оценка сложности вычисления характеристической функции свойства гиперграфов не содержать изолированных вершин. Показано, что для любого натурального к, к > 2, существует последовательность булевых функций такая, что сложность недетерминированных /¿-программ в сверхполиномиальное (по числу переменных булевой функции) число раз превосходит сложность \к In /¿/In 2 + С]-программ [С — константа, не зависящая от к), вычисляющих функции из этой последовательности.

Предложен метод получения нелинейных нижних оценок сложности детерминированных и недетерминированных программ, вычисляющих булевы функции. С его помощью получена оценка f2(nlog п/ log logn) для сложности детерминированных и недетерминированных программ, вычисляющих характеристические функции кодов Рида-Маллера и БЧХ-кодов (при некоторых значениях параметров этих кодов).

Введена операция монотонного расширения булевой функции. Показано, что операции геометрического проектирования и монотонного расширения булевой функции могут приводить к существенному росту сложности схем, вычисляющих булевы функции для некоторых моделей вычисления, в том числе, для программ и для /¿-программ. Указывается на связь между операцией геометрического проектирования и монотонного расширения булевых функций. Основные результаты диссертации опубликованы в работах автора [26]-[49], [96]-[99].

Диссертация состоит из введения, пяти глав и списка литературы. СОДЕРЖАНИЕ РАБОТЫ

1. Августинович С. В. Об одном подходе к получению нижних оценок сложности для булевых функций // Методы дискретного анализа в теории булевых функций и схем. Сб. науч. тр. — Вып. 35.- Новосибирск: Ин-т математики СО АН СССР, 1980. С. 3-9.

2. Андреев А. Е. Об одном методе получения нижних оценок сложности индивидуальных монотонных функций // Докл. АН СССР. — 1985. Т. 282, №5. - С. 1033-1037.

3. Гринчук М. И. О сложности реализации симметрических булевых функций контактными схемами: Дис. канд. физ.-мат. наук: 01.01.09. М., 1989.

4. Гринчук М. И. О сложности реализации симметрических булевых функций контактными схемами // Математические вопросы кибернетики. Вып. 3. - М.: Наука, 1991,- С. 77-114.

5. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. // Лекции по теории графов — М.: Наука, 1990.- 384 с.

6. Здобнов С. В. Алгоритм синтеза минимальных П-схем без нулевых цепей, реализующих характеристические функции линейных кодов // Комбинаторно-алгебраические методы и их применение. — Горький: Горьковский госуниверситет, 1987. — С. 27-34.

7. Здобнов С. В. О сложности реализации кодовых функций в классе контактных схем без нулевых цепей // Методы дискретного анализа в исследовании функциональных систем. Сб. науч. тр. — Вып. 47. — Новосибирск: Ин-т математики СО АН СССР, 1988. С. 47-60.

8. Касим-Заде О. М. О сложности реализации функций в одном классе алгоритмов // Материалы IX Межгосударственной школы-семинара "Синтез и сложность управляющих систем". — М.: Изд-во мех.-мат. фак-та МГУ, 1999. С. 25-30.

9. Колмогоров А. П. Три подхода к определению понятия "количество информации"// Проблемы передачи информации. — 1965. Т. I, вып.1. - С. 3-11.

10. Кузнецов С. Е. Схемы из функциональных элементов без нулевых цепей в базисе V, // Известия вузов. Математика. — 1981. — № 5. С. 56-63.

11. Кузнецов С. Е. Влияние нулевых цепей на сложность контактных схем // Вероятностные методы и кибернетика. — Вып. 20. — Казань: Изд-во Казанского ун-та, 1984. — С. 61-87.

12. Кузьмин В. А. Оценка сложности реализации функций алгебры логики простейшими видами бинарных программ // Методы дискретного анализа в теории кодов и схем. Сб. научн. тр. — Вып. 29. Новосибирск: Ин-т математики СО АН СССР, 1976. - С. 11-39.

13. Лупанов О. Б. О вентильных и контактно-вентильных схемах // Докл. АН СССР. 1956. - Т. 111, № 6 - С. 1171-1174.

14. Лупанов О. Б. О синтезе некоторых классов управляющих систем // Проблемы кибернетики. — Вып. 10. — М.: Наука, 1963. — С. 63-97.

15. Лупанов О. Б. К вопросу о реализации симметрических функций алгебры логики контактными схемами // Проблемы кибернетики. — Вып. 15. М.: Наука, 1965. - С. 85-101.

16. Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. — М.: Связь, 1979. — 744 с.

17. Нечипорук Э. И. Об одной булевской функции // Докл. АН СССР. 1966. - Т. 169, №4. - С. 765-766.

18. Нигматуллин Р. Г. Нижние оценки сложности и сложность универсальных схем. — Казань: Изд-во Казан, ун-та, 1990. — 112 с.

19. Нигматуллин Р. Г. Сложность булевых функций. — М.: Наука, 1991. 240 с.

20. Окольнишникова Е. А. О сравнении сложностей реализации булевых функций и их проекций / / Методы дискретного анализа в теории управляющих систем: Сб. науч. тр. — Вып. 31. — Новосибирск: Ин-т математики СО АН СССР, 1977. С. 76-80.

21. Окольнишникова Е. А. О влиянии одного типа ограничений на сложность схем из функциональных элементов // Методы дискретного анализа в теории управляющих систем: Сб. науч. тр.- Вып. 36. — Новосибирск: Ин-т математики СО АН СССР, 1981.- С. 46-58.

22. Окольнишникова Е. А. О сведении оценок сложности в полном базисе к оценкам сложности в неполном базисе // Методы дискретного анализа в теории графов и схем: Сб. науч. тр. — Вып. 42.- Новосибирск: Ин-т математики СО АН СССР, 1985. С. 80-90.

23. Окольнишникова Е. А. Об одном соотношении сложностей булевых функций // Проблемы теоретической кибернетики. VIII Всесоюз. науч. конф. (Горький, июль 1988 г.). Тез. докл. — Горький: Горьковский гос. пед. институт, 1988. — С. 63.

24. Окольнишникова Е. А. Нижние оценки сложности реализации булевых функций бинарными программами // Логика и семантическое программирование (Вычислительные системы). Сб. научн. тр.- Вып. 146. — Новосибирск: Ин-т математики СО АН СССР, 1992.- С. 177-180.

25. Окольнишникова Е. А. О нижних оценках сложности для бинарных программ // Сб. трудов IV Межгос. семинара по дискретной математике и ее приложениям (Москва, 2-4 февраля 1993 г.). М.: Изд-во мех.-маг. фак-та МГУ, 1993. - С. 79.

26. Окольнишникова E. А. Об одном соотношении сложностей бинарных ¿¿-программ // Проблемы теоретической кибернетики. XI Междунар. конф. (Ульяновск, 10-14 июня 1996 г.). Тез. докл. — Москва: Изд. центр РГГУ, 1996. С. 153-154.

27. Окольнишникова Е. А. Об иерархии бинарных fc-программ // II Сибирский Конгресс по Прикладной и Индустриальной Математике, ИНПРИМ-96. (Новосибирск, 27-31 мая 1996). Тез. докл. — Новосибирск: Изд-во Института математики СО РАН, 1996. С. 122.

28. Окольнишникова E. А. О сложности ветвящихся программ // Материалы IX Межгосударственной школы-семинара "Синтез и сложность управляющих систем" (Нижний Новгород, 16-19 декабря 1998). М.: Изд-во мех-мат. фак-та МГУ, 1999. - С. 63-70.

29. Окольнишникова Е. А. О двух операциях над булевыми функциями // Дискрет, анализ и исслед. операций. Сер. 1. — 2000. Т. 7, № 1. - С. 79-93.

30. Окольнишникова Е. А. Об одном методе получения нижних оценок сложности реализации булевых функций недетерминированными ветвящимися программами // Дискрет, анализ и исслед. операций. Сер. 1. 2001. - Т. 8, № 4. - С. 76-112.

31. Окольнишникова Е. А. Сложность ветвящихся программ //' Математические вопросы кибернетики. Вып. 10. — М.: Физматлит, 2001. С. 69-82.

32. Окольнишникова Е. А. О сложности недетерминированных ветвящихся программ, реализующих характеристические функции кодов Рида-Маллера // Дискрет, анализ и исслед. операций. Сер. 1. 2003. Т. 10, № 3. С. 67-81.

33. Окольнишникова Е. А. О сложности ветвящихся программ // Материалы VIII Международного семинара "Дискретная математика и ее приложения"(Москва, 2-6 февраля 2004 г.). — М.: Изд-во мех.-мат. фак-та МГУ, 2004. С. 85-86.

34. Окольнишникова Е. А. Нижние оценки сложности ветвящихся программ // Вестник Томского гос. университета. Приложение. — 2006. № 17. - С. 42-46.

35. Пулатов А. К. О сложности реализации характеристических функций плотно упакованных (гг, 3)-кодов в классе П-схем // Дискретный анализ. Сб. науч. тр. — Вып. 22.— Новосибирск: Ин-т математики СО АН СССР, 1973. С. 53-56.

36. Пулатов А. К. Нижняя оценка сложности схемной реализации для одного класса кодов / / Дискретный анализ (Синтез схем и автоматов). Сб. науч. тр. — Вып. 25.— Новосибирск: Ин-т математики СО АН СССР, 1974. С. 56-61.

37. Пулатов А. К. О влиянии нулевых цепей на сложность реализации булевых функций контактными схемами // Методы дискретного анализа в решении комбинаторных задач. Сб. науч. тр. — Вып. 30. Новосибирск: Ин-т математики СО АН СССР. - 1977. - С. 30-37.

38. Пулатов А. К. Нижние оценки сложности реализации характеристических функций групповых кодов П-схемами // Комбинаторно-алгебраические методы в прикладной математике. — Горький: Горьковский госуниверситет, 1979. — С. 81-95.

39. Разборов А. А. Нижние оценки сложности монотонной сложности некоторых булевых функций булевых функций контактно-вентильными схемами // Докл. АН СССР. 1985. - Т. 281, № 4. -С. 798-801.

40. Разборов А. А. Нижние оценки сложности реализации симметрических булевых функций контактно-вентильными схемами // Мат. заметки. 1990. - Т. 48, вып. 6. - С. 79-90.

41. Рычков К. Л. Модификация метода В.М. Храпченко и применение ее к оценкам сложности П-схем для кодовых функций // Методы дискретного анализа в теории графов и схем: Сб. науч. тр. — Вып. 42,— Новосибирск: Ин-т математики СО АН СССР, 1985. — С. 91-98.

42. Сидельников В. М. Код с исправлением ошибок // Математическая энциклопедия. — М.: Советская энциклопедия, 1979. — Т. 2. — С. 930-934.

43. Субботовская Б. А. О сравнении базисов при реализации функций алгебры логики формулами // Докл. АН СССР. — 1963. — Т. 149, №4. С. 784-787.

44. Храпченко В. М. О сложности реализации линейной функции в классе П-схем // Мат. заметки. — 1971. Т. 9, № 1. — С. 35-40.

45. Храпченко В. М. Об одном методе получения нижних оценок сложности П-схем // Мат. заметки. — 1971. — Т. 10, № 1. — С. 83-92.

46. Храпченко В. М. Нижние оценки сложности схем из функциональных элементов (обзор) // Кибернетический сборник. — М., 1984. Вып. 21. - С. 3-54.

47. Ablayev F., Gainutdinova A., Karpinski M., Moore C, Pollett C. On the computational power of probabilistic and quantum branching program // Inform, and Comput. — 2005. — V. 203, N. 2. — P. 145-162.

48. Ajtai M. A non-linear time lower bound for Boolean branching programs // Proc. of the 40th Annual Symposium on Foundations of Computer Science, FOCS '99 (New York, October 17-19, 1999). Los Alamitos: IEEE Computer Society, 1999. - P. 60-70.

49. Alon N., Maass W. Meanders and their applications in lower bound arguments // J. Comput. System Sci. — 1988. — V. 37, N 2. — P. 118-129.

50. Babai L., Hajnal P., Szemeredi E., Turan G. A lower bound for read-once-only branching programs // J. Computer and System Sci. — 1987. V. 35, N 2. -P. 153-162.

51. Babai L., Pudlak P., Rodl V., Szemeredi M. Lower bounds to the complexity of symmetric Boolean functions // Theoret. Comput. Sci. — 1990. V. 74. - P. 313-324.

52. Barrington D. A. M., Straubing H. Superlinear lower bounds for bounded-width branching programs //J. Computer and System Sci. — 1995. V. 50, N 3. — P. 374-381.

53. Beame P., Jayram T. S., Saks M. Time-space tradeoffs for branching programs //J. Computer and System Sci. — 2001. — V. 63, N 4. P. 542-572.

54. Bollig B. Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication // Theoret. Inform. Appl. 2001. - V. 35, N 2. - P. 149-162.

55. Bollig B., Sauerhoff M., Seiling D., Wegener I. Hierarchy theorems for kOBDDs and kIBDD // Theoret. Comput. Sci. 1998.- V. 205 P. 45-60.

56. Bollig B., Wegener I. Completeness and noncompleteness results with respect to read-once projections // Inform, and Comput. — 1998. — V. 143, N 1. P. 24-33.

57. Bollig B., Wegener I. A very simple function that requires exponential size read-once branching programs // Inform. Processing Letters. — 1998. V. 66, N 2. - P. 53-57.

58. Bollig B., Wegener I. Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams // Theory Comput. Syst.- 1999. V. 32, N 4.- P. 487-503.

59. Bollig B., Sauerhoff M., Wegener I. On the nonappoximability on boolean functions by OBDD and read-fc-times branching programs // Inform, and Comput. 2002. -V. 178. - 263-278.

60. Borodin A., Razborov A., Smolensky R. On lower bounds for read-/c-times branching programs // Computational Complexity. — 1993. V. 3, N 1. - P. 1-18.

61. Bryant R. E. Graph-based algorithms for Boolean function manipulation // IEEE Trans. Computers. — 1986. — V. 35. — P. 677-691.

62. Bryant R. E. On the complexity of VLSI implementation and graph representations of Boolean functions with application to integer multiplication // IEEE Trans. Computers. 1991. — V. 40, N 2. — P. 205-213.

63. Bryant R. E. Symbolic Boolean manipulation with ordered binary decision diagrams // ACM Computing Surveys. — 1992. — V. 24, N 3.- P. 293-318.

64. Cobham A. The recognition problem for the set of perfect squares // Proc. of the 7th Symposium on Switching an Automata Theory (SWAT).- 1966. P. 78-87.

65. Giel O. Branching program size is almost linear in formula size //J. Computer and System Sci. 2001. - V. 63, N 2. - P. 222-225.

66. Jukna S. A note on read-k times branching programs // RAIRO Inform. Theor. Appl. 1995. - V. 29, N 1. - P. 75-83.

67. Lafferty J., Vardy A. Ordered binary decision diagrams and minimal trellises // IEEE Trans. Computers. 1999. - V. 48, N 9. - P. 971-986.

68. Okol'nishnikova E. A. Lower bounds on branching programs // Siberian Adv. Math. 1993. - V. 3, N 1. - P. 152-166.

69. Okol'nishnikova E. A. On some operations over Boolean functions // Proc. of the seminar "The complexity of Boolean functions"(Dagstuhl, 31 октября 5 ноября 1999 г.) — Germany, Dagstuhl, 1999. — P. 10.

70. Pudläk P. The hierarchy of Boolean circuits // Computers and Artificial Intelligence. 1987. - V. 6, N 5. - P. 449-468.

71. Pudläk P., Zak S. Space complexity of computations // Technical Report. — 1983. — Univ. Prague.

72. Riordan J., Shannon C. The number of two-terminal series parallel nerworks //J. Math. Phys. 1942. - V. 21, N 2. - P. 83-93. (Русский перевод: Шеннон К. Работы по теории информации и кибернетике. - М.: ИЛ, 1963. - С. 46-58).

73. Sauerhoff М. Complexity theoretical results for randomized branching programs // Dissertation zur Erslangung des Grades eines Doktors der Naturwissenschaften der Universität Dortmund am Fachbereich Informatic. — Dortmund, 1998.

74. Sauerhoff M., Sieling, D. Quantum branching programs and space-bounded nonuniform quantum complexity. (English summary) Theoret. Comput. Sci. 2005. - V. 334, N. 1-3. P. 177-225.

75. Savincky P., Zak S. A large lower bound for 1-branching programs, // ECCC, revision 01 of Technical report 96-036. — Electronic Colloquim on Computational Complexity. — 1996. — available at http://www. eccc. uni-trier .de / eccc /.

76. Shannon C. The synthesis of two-terminal switching circuits // Bell. Syst. Techn. J. V. 28, N 1. - 1949. - P. 59-98. (Русский перевод: Шеннон. К. Работы по теории информации и кибернетике. — М.: ИЛ, 1963. - С. 59-101).

77. Sieling D. New lower bounds and hierarchy results for restricted branching programs //J. Comput. System Sci. — 1996. — V. 53, N 1. P. 79-87.

78. Thathachar J. S. On separating the read-&-times program hierarchy // Proc. of the 30th Ann. ACM Symp. on Theory of Computing, STOC'98 (Dallas, May 23-26, 1998). New York: ACM, 1999. -P. 653 662.

79. Wegener I. The complexity of Boolean functions. — Stuttgart: B. G. Teubner; Chichester: John Wiley & Sons, 1987. 457 p.

80. Wegener I. On the complexity of branching programs and decision trees for cligue functions // J. of the Assoc. Сотр. Mach. — 1988. — V. 35, N 2. P. 461-471.

81. Wegener I. Efficient data structures for Boolean functions // Discrete Mathematics. 1994. - V. 136. - P. 347-372.

82. Wegener I. Branching programs and binary decision diagrams. Theory and applications. — Philadelphia, PA: SIAM, 2000. 408 p.

83. Wegener I. Complexity theory. Exploring the limits of efficient algorithms. — Berlin: Springer-Verlag, 2005. — 308 pp.

84. Wei V. K. Generalized Hamming weights for linear codes // IEEE Trans, on Inform. Theory. V. 37, N 5. - 1991. -P. 1412-1418.