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

Введение

Глава 1. Пороговые суммы

1.1. Продолжение частичных функций.

1.2. Теорема о пороговых суммах.

1.3. Следствия теоремы о пороговых суммах.

Глава 2. Сложность сужений булевых функций.

Схемы из функциональных элементов

2.1. Нижние оценки сложности сужений.

2.2. Максимально сложные сужения.

2.3. Функции с малым числом единиц.

2.4. Экстремальные сужения.

Глава 3. Схемы из функциональных элементов.

Свойства и применения сужений

3.1. Разложение булевых функций.

3.2. Условия существования разложений.

3.3. Сложность разложений.

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

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

Глава 4. Сложность сужений булевых функций.

Контактные схемы и формулы

4.1. Нижние оценки сложности сужений. Общая теорема

4.2. Нижние оценки сложности сужений для контактных схем.

4.3. Нижние оценки сложности сужений для формул

СОДЕРЖАНИЕ

Глава 5. Локальная сложность булевых функций

5.1. Определения.

5.2. Операторы сжатия.

5.3. Локально сложные функции.

5.4. Локально простые функции.

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

6.1. Определения.

6.2. Приведенные программы.

6.3. Элементарные функции.

6.4. Свойства среднего времени и свойства неветвящихся программ.

Глава 7. Неветвящиеся программы с условной остановкой. Сложность сужений

7.1. Функции Шеннона для среднего времени.

7.2. Оценки числа программ.

7.3. Нижние оценки среднего времени.

7.4. Верхние оценки среднего времени.

7.5. Частичные булевы функции.

7.6. Сложность сужений.

7.7. Экстремальные сужения.

Глава 8. Вероятностные неветвящиеся программы с условной остановкой

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

8.2. Надежные вероятностные программы.

8.3. Вероятностные программы с надежностью меньшей единицы.

8.4. Общий случай.

8.5. Экстремальные сужения.

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

Каждое сужение, по своему определению, является частичной функцией. Интерес к частичным функциям возник достаточно давно и в течении последних тридцати лет оставался на достаточно высоком уровне. Исследовалась сложность частичных функций, определенных на областях различной мощности [1, 22]. Изучались приложения частичных функций к различным задачам теории сложности. Здесь прежде всего нужно отметить работы Э.И. Нечипорука [13] и А.Б. Андреева [2], касающиеся самокорректирующихся вычислений, в которых частичные функции играли существенную роль. Естественным образом частичные функции возникали при анализе различных вероятностных вычислений [18], приближенной реализации булевых функций [24]. Однако, как правило, частичные функции исследовались в шенноновской постановке: вводился некоторый класс частичных функций и изучалась сложность самых сложных функций из этого класса. В результате получались утверждения о самых сложных или о "почти всех" функциях данного класса.

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

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

Пусть f{x 1,., хп) — произвольная булева функция. Сложностью £(/) функции / называется число элементов в минимальной схеме из функциональных элементов, реализующей функцию / в базисе {Х/,&,—}. Сужением функции / : {0,1}п —> {0,1} на область В С {0,1}п называется частичная функция К : В —> {0,1} такая, что при всех х £ £) справедливо равенство f(x) = Ъ,{х). Сужение функции / на область Б будем обозначать через /д.

Пусть Б С {0,1}п, / : В —>• {0,1}, 5 = {5г-} — множество минимальных схем, реализующих частичную функцию /. Каждая в г € ¿> реализует некоторую полностью определенную функцию /¿. Упорядочим эти функции, сравнивая их векторы значений как целые числа. Минимальную среди /г функцию назовем продолжением функции / на {0,1}п. Понятие продолжения функции позволяет рассматривать частичные булевы функции как полностью определенные.

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

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

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

Известно, что любой вещественный многочлен степени к — 1 однозначно определяется по своим значениям в к точках не лежащих на кривой к — 2)-й степени. Поэтому можно говорить, что вся информация о многочлене конечной степени содержится в конечном числе точек. Аналогичным свойством обладают булевы функции. Любая булева функция п переменных, степень многочлена Жегалкина которой не превосходит к, однозначно определяется по своим значениям в шаре радиуса к с центром в нулевом наборе. Следовательно вся информация о булевой функции конечной степени содержится в шаре конечного радиуса.

Приведенные примеры порождают естественный вопрос, формулируемый для булевых функций следующим образом:

Можно ли для произвольной булевой функции / указать в булевом кубе такие область или систему областей, что значения функции на наборах из этих областей будут однозначно определять /?

На этот вопрос в диссертации дается положительный ответ — для каждой функции /, зависящей от п переменных, можно указать не более п таких областей, мощности которых незначительно превосходят величину сложности /, что функция / однозначно определяется по своим значениям в этих областях. Заметим, что количество информации*), необходимое для определения /, оказалось тесно связанным со сложностью / чем сложнее функция, тем на большем числе наборов надо знать ее значения. Поставленный вопрос связан с различными аспектами сложности вычисления булевых функций. Один из них — получение нижних оценок сложности сужений булевых функций. Известно [1, 17], что любая область в булевом кубе может быть достаточно хорошо сжата при помощи линейных [1, 9, 21] и нелинейных простореализуемых [22] булевых операторов. При этом легко показать, что сложность сжатия областей полиномиальной мощности при помощи линейных операторов имеет линейную сложность. Поэтому частичная функция, определенная на области небольшого размера и имеющая нелинейную схемную сложность, в некотором смысле эквивалентна экспонециально сложным функциям и доказать для такой частичной функции небольшую нелинейную, и даже линейную с подходящей мультипликативной константой, оценку сложности ни чуть не легче, чем установить экспоненциальную нижнюю оценку для сложности полностью определенной булевой функции. Таким образом представляется достаточно естественным попытаться объяснить существующие в настоящее время трудности с получением даже не очень высоких нижних оценок сложности существованием у булевых функций достаточно сложных сужений**) Используя подобные рассуждения в частном случае ранее удалось показать [19, 20], что доказательство невысоких линейных нижних оценок сложности порождения графов влечет доказа-тёльство экспонециальных нижних оценок сложности булевых функций. В связи с этим для произвольной булевой функции / и целого параметра й в диссертации исследуются следующие вопросы:

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

Как велика может быть сложность сужения функции / на некоторую область мощности с? и как сильно эта сложность может отличаться от сложности /?

Как сильно может отличаться сложность самого сложного сужения функции /, среди ее сужений на области мощности с1, от сложности самой сложной частичной функции, определенной на области мощности <11

С двумя этими вопросами связан еще один вопрос, который мы сформулируем следующим образом:

Существует ли для произвольной булевой функции область в {0,1}п, в которой "локализована" значительная часть ее сложности, или же такой области нет и сложность функции "размазана" по всему булевому кубу?

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

Рассмотрим содержание и перечислим основные результаты настоящей диссертации.

В первой главе диссертации рассматривается представление произвольной булевой функции в виде пороговой суммы некоторого числа ее сужений, т. е. в виде (1) где М — функция голосования и при всех г Е {1,.,мощности областей Д С {0,1}п не превосходят п4Ь(/), и 8 < п. Существование такого представления доказывается в теореме 1.1 для различных управляющи-их систем. Из этой теоремы немедленно следует, что для любой булевой функции / от п переменных можно указать не более п областей таких, что их мощности не более чем в п4 раз превышают сложность функции /, а сама функция / однозначно определяется по своим значениям в этих областях, т. е. вся информация о функции содержится в этих областях.

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

Во второй главе диссертации рассматриваются две задачи. Первая заключается в следующем: для произвольной булевой функции / и множества М, состоящего из всех областей из {0,1}п, имеющих фиксированную мощность б?, требуется установить нижнюю оценку для сложности самого сложного сужения / на области из М при реализации / схемами из функциональных элементов. Вторая задача является в некотором смысле предельным случаем первой. Она формулируется следующим образом: для произвольной булевой функции / требуется установить нижнюю оценку для сложности самого сложного сужения /о, удовлетворяющего с точностью до постоянного множителя равенству Ь(/г>) log L(/d) = |jD|*). Сложность сужения в первом случае оценивается через сложность рассматриваемой функции и мощность области сужения, во втором случае — через сложность функции и число ее аргументов.

Результаты, относящиеся к решению первой задачи, содержатся в теореме 2.1. Из этой теоремы следует, что у любой функции / от п переменных, сложность которой L(f) по крайней мере квадратична, существует область полиномиальной относительно L(f) мощности, сложность сужения функции / на которую по порядку не более чем в п/ log п раз отличается от L(f).

Установленные в теореме 2.3 верхние оценки для сложности сужений функций полиномиального веса показывают, что нижняя оценка из теоремы 2.1 оптимальна по порядку, т. е. существуют функции, для которых сложность любого сужения на область данной мощности по порядку не превосходит нижней оценки из этой теоремы. Доказательство теоремы 2.3 в существенной степени опирается на лемму 2.12, обобщающую известные результаты Лупанова [11] и Шоломова [22].

Решение второй задачи содержится в теореме 2.2. Эта теорема показывает, что для любой булевой функции от п переменных, сложность реализации которой схемами из функциональных элементов превышает величину п2+£, е — сколь угодно малая положительная константа, можно найти такую область D, что сужение функции на D имеет нелинейную сложность, которая лишь в фиксированное число раз отличается от сложности самой сложной определенной на D функции. Теорема 2.2 позволяет перенести на произвольные булевы функции ряд "плохих" свойств, которыми обладают функции, имеющие максимальную по порядку сложность. Среди этих "плохих" свойств наибольший интерес представляют следующие два.

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

Как уже упоминалось выше, в третьей главе диссертации устанавливаются необходимые условия существования представления (1) для схем из функциональных элементов. Для этого рассматривается специальный вариант представления булевых функций в виде пороговых сумм — (s, d, е)-разложение. Будем говорить, что для функции / имеет место (s, d, е)

Всюду далее log обозначает логарифм по основанию 2. разложение, если при каждом х € {0,1}" справедливо неравенство в <1, 3=1 где б > 0, целые положительные в и I связаны соотношением I < — б) в, и | < (1 при всех 3 €{1,2,., а}. Понятие (з, с?, е)-разложения является более сильным по сравнению с понятием пороговой суммы — в б)-разложении требуется, чтобы доля частичных функций, значения которых совпадают с соответствующим значением исходной функции, была строго отделена от Достаточное условие сформулировано в теореме 3.2. Эта теорема вытекает из теоремы 3.1, которая в является тривиальным следствием теоремы 1.1 и приводится без доказательства.

Необходимые условия существования (в, б)-разложений, теоремы 3.3 и 3.5, найдены в форме соотношений, связывающих сложность функции и параметры ее с?, б)-разложения, величины « и (I, между собой. Показано, что для достаточно широкого множества значений параметров разложения установленные соотношения являются точными по порядку. Установлены оценки минимально возможных значений параметров ей при которых рассматриваемые разложения существуют. В частности показано, что сложность функции не может превышать величину параметра с? более чем в п раз (теорема 3.5), т. е. знание сужений булевой функции даже на достаточно большое число областей маленького размера не позволяет вычислить ее значение на произвольном наборе.

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

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

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

В четвертой главе диссертации для контактных схем и формул устанавливаются нижние оценки для сложности самого сложного сужения произвольной функции / на области данной мощности. Для контактных схем в теореме 4.2 получены результаты достаточно близкие к соответствующим результатам для схем из функциональных элементов. Результаты для формул, теорема 4.3, несколько слабее. Оценки для формул, близкие к соответствующим оценкам для схем из функциональных элементов, установлены для "почти всех" функций в теореме 4.4.

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

Пусть Б С {0,1}п, / : {0,1}п —> {0,1}. Будем говорить, что линейный булев (п, т)-оператор ^ сжимает область I), если т < ии^(ж) ф Р(у) ПРИ всех ж, у € Б. Функция /, область Б и оператор ^ порождают функцию /д^ : {0,1}т {0,1} такую, что = Дж)5 если -Р(ж) = у. Сложность порожденных таким образом функций будем называть локальной сложностью.

Дадим два неформальных определения.

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

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

В пятой главе вводятся классы локально сложных и локально простых булевых функций. В теоремах 5.1 и 5.6 доказывается инвариантность этих классов относительно полиномиально эквивалентных мер сложности. При помощи теоремы 1.1 доказываются достаточные условия принадлежности булевых функций классам локально сложных функций для различных управляющих систем. Условия принадлежности формулируются в терминах сложности функций. Рассматривается связь между доказательством принадлежности функции классу локально сложных функций и доказательством нижних оценок сложности для схем из функциональных элементов, контактных схем, формул и 7г-схем.

В шестой, седьмой и восьмой главах диссертации изучается среднее время вычисления значений булевых функций неветвящимися программами с условной остановкой. Неветвящейся программой с условной остановкой назывется последовательность операторов, каждый из которых вычисляет некоторую двухместную булеву функцию. Аргументами каждого оператора могут быть либо величины полученные в результате выполнения предыдущих операторов, либо значения независимых переменных. Некоторые операторы могут прекращать выполнение программы. В отличии от обычных неветвящихся программ изоморфных схемам из функциональных элементов и затрачивающих одинаковое число шагов при работе на различных аргументах, время работы рассматриваемых программ для разных аргументов может быть различным. Естественной мерой сложности таких программ является среднее время их работы. В диссертации рассматриваются так же вероятностные программы с условной остановкой. Отличие вероятностных программ от обычных (детерминированных) состоит в том, что они содержат операторы, порождающие с равными вероятностями либо 0, либо 1. Поэтому результатом работы вероятностной программы является не число, а некоторая случайная величина.

Пусть Р — неветвящаяся программа. Время работы неветвящейся программы Р на наборе переменных х, т. е. число операторов этой программы, выполненных до ее остановки, обозначим через Тр(х). Величину Т(Р) = YlxeD Тр{х) назовем средним временем работы программы Р на области D. Величину Т(д) = min Т(Р), где минимум берется по всем программам, вычисляющим д, назовем средним временем вычисления частичной функции д.

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

В седьмой главе изучаются функции Шеннона для различных классов булевых функций, а также сложность сужений с точки зрения среднего случая. В теореме 7.1 для булевых операторов с растущим числом компонент установлены асимптотически точные формулы для функций Шеннона. Из теоремы 7.1 следует, что для почти всех булевых функций среднее время, затрачиваемое на вычисление их значений, только в постоянное число раз меньше времени, используемого обычными неветвя-щимся программами, т.е. возможность досрочной остановки вычислений позволяет уменьшить время работы в среднем не более чем в постоянное число раз. Также в этой главе найдены точные по порядку формулы для частичных булевых функций и частичных функций с данным числом единичных значений. В теореме 7.4 показано, что для почти всех частичных функций п аргументов, принимающих единичные значения не более чем на бесконечно малой доле наборов из области определения, среднее время (с точностью до постоянного множителя) не зависит от размера области определения. Если размер области определения экспоненциален, а вес функции является полиномом от числа переменных, то среднее время вычисления почти всех таких функций почти в п раз меньше времени, необходимого в худшем случае. В теореме 7.5 для произвольной булевой функции найдены нижние оценки среднего времени вычисления ее сужений на области различных размеров. Далее в этой главе показано, что эти оценки оптимальны по порядку.

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

Для многих практически важных задач не известны хорошие алгоритмы, решающие эти задачи за полиномиальное, относительно размера входа, время. В то же время эти задачи могут быть решены достаточно быстро в "среднем", т. е. существуют алгоритмы, быстро решающие задачи для почти всех входных данных. Однако, как правило, для каждого алгоритма, решающего быстро в "среднем" одну из таких задач, можно найти входные данные, на которых этот алгоритм работает долго. Ранее неоднократно высказывалось мнение [5, 7, 17], что вероятностные алгоритмы — алгоритмы, использующие в процессе работы датчики случайных чисел, лишены этого недостатка. Это мнение обосновывалось тем, что время работы алгоритма усредняется не только по входным данным, но и по величинам, полученным с помощью датчиков случайных чисел.

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

Аналогичные результаты получены для вычисления булевых функций произвольными вероятностными программами. Для программ, надежность которых не меньше 3/4, в теореме 8.4 установлены результаты, аналогичные соответствующим результатам для надежных вероятностных программ. Нетрудно показать, что все результаты остаются справедливым для любой надежности, строго большей 1/2.

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

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

1. Андреев А. Е., О сложности реализации частичных булевых функций схемами из функциональных элементов, Дискретная математика. Вып. 4 (1989), С. 36-45

2. Андреев А. Е., О синтезе функциональных сетей, Дисс. доктора физ.-мат. наук., М.:МГУ, 1985.

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

4. Вэльянт Л., Простые монотонные формулы для функции голосования, Кибернетический сборник, Вып. 24. М.:Мир, 1987, С. 97-100

5. Карп Р., Комбинаторика, сложность и случайность, Лекции лауреатов премии Тьюринга, М.:Мир, 1993, С. 498-521

6. Красулина Е. Г., О сложности реализации монотонных симметрических функций алгебры логики контактными схемами, Математические вопросы кибернетики, Вып. 1. М.: Наука, 1988, С. 140167

7. Кук С., Обзор вычислительной сложности, Лекции лауреатов премии Тьюринга, М.:Мир, 1993, С. 475-497

8. Лидл Р., Нидеррайтер Г., Конечные поля, М.: Мир, 1988.

9. Ложкин С. А., Семенов A.A., Об одном методе сжатия, Известия ВУЗ. Вып. 7 (1988), С. 44-52

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

11. Лупанов О. Б., Об одном подходе к синтезу управляющих систем — принципе локального кодирования, Проблемы кибернетики, Вып. 14. М.:Наука, 1965, С. 31-110

12. Лупанов О. В., Асимптотические оценки сложности управляющих систем., М.: МГУ, 1984.

13. Нечипорук Э. И., О топологических принципах самокорректирования, Проблемы кибернетики, Вып. 21. М.:Наука, 1969, С. 5-102

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

15. Нигматуллин Р.Г., Нижние оценки сложности и сложность универсальных схем, Казань.: КГУ, 1990.

16. Редькин Н.П., Надежность и диагностика схем, М.: МГУ, 1992.

17. Тарьян Р., Сложность комбинаторных алгоритмов, Кибернетический сборник, Вып. 17. М.:Мир, 1980, С. 61-113

18. Фрейвалд Р.В., Ускорение распознавания некоторых множеств применением датчика случайных чисел, Проблемы кибернетики, Вып. 36. М.:Наука, 1979, С. 209-224ЛИТЕРАТУРА141

19. Чашкин А. В., О сложности булевых матриц, графов и соответствующих им булевых функций, Дискретная математика. Вып. 21994), С. 43-73

20. Чашкин А. В., О сложности конечных графов, ДАН. Т. 340, Вып.61995), С. 748-750

21. Чашкин А. В., О сжатии областей булева куба линейными булевыми операторами, Труды III Международной конференции "Дискретные модели в теории управляющих систем" (Красновидово, 1998), С. 114-117

22. Шоломов Л. А., О реализации недоопределенных булевых функций схемами из функциональных элементов, Проблемы кибернетики, Вып. 21. М.:Наука, 1969, С. 215-226

23. Adleman L., Two theorems on random polynomial time., Proc. 19th. Symp. on Foundations of Computer Science. IEEE Computer Society, Los Angeles, 1978, pp. 75-83.

24. Pippenger N., Information Theory and the Complexity of Boolean Functions, Mathematical System Theory. 10 (1977), 129-167.

25. Uhlig D., Combinatorial Networks which are Self-Correcting and have almost the Smallest Complexity., Wiss. Beitraege der FSU Jena, Kompliziertheit von Lern- und Erkennungsprozessen, 1975, pp. 225-228.

26. Чашкин А. В., Об оценках сложности сужений булевых функций, ДАН Т. 348, Вып. 5 (1996), С. 595-597

27. Чашкин А. В., О сложности сужений булевых функций, Дискретная математика. Вып. 2 (1996), С. 133-150

28. Чашкин А. В., О сложности и глубине схем, реализующих частичные булевы функции, Дискретная математика. Вып. 2 (1997), С. 53-58

29. Чашкин А. В., О среднем времени вычисления значений булевых функций, Дискретный анализ и исследование операций. Сер. 1. Вып. 1 (1997), С. 60-78

30. Чашкин А. В., Нижние оценки сложности сужений булевых функций, Дискретный анализ и исследование операций. Сер. 1. Вып. 2 (1997), С. 75-111

31. Чашкин А. В., О вычислении булевых функций вероятностными программами, Дискретный анализ и исследование операций. Сер. 1. Вып. 3 (1997), С. 49-68

32. Чашкин А. В., Локальная сложность булевых функций, Дискретный анализ и исследование операций. Сер. 1. Вып. 3 (1997), С. 69-80

33. Чашкин А. В., Самокорректирующиеся схемы для функций полиномиального веса, Вестн. Моск. Ун-та. Сер.1. Математика. Механика. Вып. 5 (1997), С. 64-66ЛИТЕРАТУРА 142

34. Чашкин А. В., О среднем времени вычисления полиномиально сводимых булевых функций, Вестн. Моск. Ун-та. Сер.1. Математика. Механика. Вып. 1 (1998), С. 68-71

35. Чашкин А. В., О среднем времени вычисления булевых операторов, Дискретный анализ и исследование операций. Сер. 1. Вып. 1 (1998), С. 88-103

36. Чашкин А. В., Сложные сужения булевых функций, Материалы XI Межгосударственной школы-семинара "Синтез и сложность управляющих систем" (Нижний Новгород, 1999), С. 93