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

Теория сложности вычислений является важным разделом математической кибернетики. Целью теории является оценивание величины ресурсов, необходимых для решения тех или иных вычислительных задач. Рассматриваются различные модели вычисления такие, например, как машины Тьюринга, автоматы, нормальные алгоритмы, схемы из функциональных элементов, формулы в различных базисах и т. д.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. Pudlak P. The hierarchy of Boolean circuits // Computers and Artificial Intelligence. 1987. — V. 6, N 5. — P. 449−468.

71. Pudlak 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 Universitat 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. TeubnerChichester: 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.