Введение к работе
Актуальность темы исследования. В основе исследований слож-ости вычислений и алгоритмов лежат доказательства нижних оце-ov сложности вычисления функций в различных модельных классах .лгоритмоп. Доказательство каждой новой нижней оценки сложно-ти ведет ко все более глубокому пониманию природы вычислений.
Традиционно базовыми модельными классами алгоритмов в тео->ии сложности являются схемы из функциональных элементов, кон-:актные схемы и алгоритмы с памятью (конечные автоматы и маши-[ы Тьюринга). Современное состояние компьютерных технологий демонстрирует практическую ценность казалось бы чисто теорети-іеских результатов теории сложности в таких модельных классах чіравляющих систем, как схемы из функциональных элементов и кон-актные схемы.
В связи с этим очень важным является анализ, систематизация >езультатов и наработанных методов теории сложности. Введете в конце семидесятых годов в изучение коммуникационной вычи-лительной модели явилось результатом обобщения и осмысления оммуникационно-информационных [методов в доказательстве ниж-:их оценок сложности.
Коммуникационно-информационные методы в теоретических ис-ледованиях применяются с момента рождения теории сложности. )ти методы эффективны там, где существенным являетсяЧзбмен ин-юрмацией между различными локйльны.ми частями исследуемой юдели вычислений. Классическим примером коммуникационного [етода доказательства нижних оценок является метод следов для дноленточных машин Тьюринга, примененный впервые в работе
'Исследования по теме диссертации частично финансировались рантами УР-11/93 (Совр. проблемы мат. и мех.). РФФИ 94-01-00117-, NSF CCR-S957604
Я.М.Барздиня в 1965 году. Метод следов и его обобщение — мето перекрытий — за последние десятилетия применялся для доказатель ства нижних оценок времени и памяти вычислений на многоленточ пых и вероятностных машинах Тьюринга.
Схемные вычислительные модели являются более "тонким инструментом" при исследовании сложностных аспектов вычислений чем вычислительные модели с памятью. Это, в частности, выражается в более разнообразном проявлении коммуникационно-информационных методов доказательств нижних оценок сложности в схемных модельных классах, чем в вычислительных моделях с памятью. Например, коммуникационный подход лежит в основе метода В.М.Храпченко доказательства нижних оценок сложности в классе П-схем. Явным образом коммуникационной подход достаточно хорошо работает для доказательства нижних оценок сложности реализации функций в схемах из клеточных элементов. В последние годь коммуникационный метод успешно применялся различными автора ми для доказательства нижних оценок сложности в схемах из поро говых элементов ограниченной глубины. По-видимому, возможное!! коммуникационных методов в теории схемной сложности далеко не исчерпаны.
Интенсивное развитие СБИС-технологий выявило существеннук зависимость времени вычислений в СБИС-чипах от площади чипа кристалла и от числа битов, необходимых дли обмена между функ циональньши элементами чипа (коммуникационной сложности, вычи сления). Первые результаты такого рода были установлены Томпсо ном.
Общепринятая абстрактная модель, ориентированная на изуче ние коммуникационной сложности для детерминированных и вероят ностных вычислений, была введена Яо в 1979 году. Содержатель» коммуникационная вычислительная модель может быть описана еле дующим о6}>азом. Имеется два вычислителя и линия связи между ни
ми, по которой они могут обмениваться последовательностями двоичных сигналов. Каждый из вычислителей получает свою часть входной информации, и они хотят совместно вычислить число, которое является функцией от обоих входов. Предполагается, что 1) оба вычислителя имеют неограниченные вычислительные возможности и 2) вычисления в самих вычислителях "ничего не стоят". Однако каждый пересылаемый бит между вычислителями имеет "стоимость". Обмен информацией (двоичными последовательностями) продолжается до тех пор пока один из вычислителей не,будет готов дать ответ.
В связи с неограниченностью вычислительных возможностей наших вычислителей и способом их общения между собой вместо понятия алгоритм используют понятие протокол. Неформально коммуникационный протокол ф — это правила, определяющие порядок пересылки и смысл пересылаемых двоичных последовательностей между вычислителями.
Сложность Сф протокола ф на данной паре входов — это общее число битов, которыми обмениваются вычислители в процессе вычисления.
В диссертации рассматривается коммуникационное вычисление булевых функций. Булева функция /:1хУ-»{0,1}в общем случае вычисляется следующим образом: последовательность х Є X подается на вход вычислителя Рь а последовательность у Є У — на вход вычислителя Р2. Вычислитель Р] первым начинает передавать информацию. После необходимого обмена информацией между вычислителями вычислитель Р2 выдает значение функции /(х,у).
Детерминированная коммуникационная сложность DC(f) булевой функции / — это minmaxIC^}, где максимум берется по всем парам (х, у) Є X х Y, а минимум — по всем детерминированным протоколам, вычисляющим функцию /.
Вероятностная коммуникационная сложность PCp(f) булевой функции / — это тіптах{Сф}, где максимум берется по всем парам
0е! у) Є X х Y, а минимум по всем вероятностным протоколам, вычисляющим функцию / с вероятностью не меньше, чем р, р > 1/2.
Теория нижних оценок коммуникационной сложности вычислений переживает в последнее десятилетие свое бурное развитие. Исследования по нижним оценкам коммуникационной сложности булевых функций начались с момента определения коммуникационной модели вычислений. В последние годы в англоязычной литературе появились обзоры по коммуникационной сложности вычислений и приложений коммуникационных методов в различных областях теории сложности и СБИС теории2.
Известные общие нижние оценки коммуникационной сложности основаны на анализе коммуникационной матрицы булевой функции. Булевой функции f с выбранным разбиением X,Y входов естественным образом соответствует коммуникационная матрица СМ/, строки котораїї. соответствуют входам изХ, а столбцы — входам изУ. На пересечении строких Є X и столбцау Є Y стоит значение f(x,y).
Для одностронних коммуникационных вычислений (только вычислитель Р\ передает сообщение вычислителю /) выполняется
DC(f) = \nrow(CMf)].
Для общего случая на сегодняшний день известно два основных метода доказательств нижних оценок коммуникационной сложности булевых функций.
Алгебраический подход, предложенный в работе К.Мельхорна и Е.Шмидта. Для детерминированных коммуникационных вы-
2см., например, обзор Л.Ловаза (Lovasz L.) Communication Complexity: A Survey в сборнике. "Paths, Flows and VLSI Layout", Korte, Lovasz, Proniel, Schrijver Eds., Springer-Verlag 1990, p. 235-266; и обзор Т.Ленгауэра (Lengauer Т.) VLSI Theory в сборнике Handbook of Theoretical Computer Science, Edited by J. van Leeuwen, Elsevier Science Publishers B. V. 1990, p. 837-868.
числений в терминах ранга коммуникационной матрицы CMf, начиная с работы К.Мельхорна и Е.Шмидта, были доказаны разные варианты нижних оценок коммуникационной сложности.
Для недетерминированных коммуникационных вычислений в терминах логарифма числа покрытий коммуникационной матрицы СМ монохромными подматрицами (Р.Липтон).
Для вероятностных коммуникационных вычислительных моделей имеются определенные достижения в доказательстве нижних оценок сложности как для почти всех булевых функций (А.Яо и др.), так и для некоторых индивидуальных функций. Наиболее высокие нижние оценки вероятностной и недетерминированной коммуникационной сложности для ряда индивидуальных естественных функций доказаны в работах А.А.Разборова.
В качестве открытых вопросов теории коммуникационной сложности и теории сложности вероятностных вычислений можно отметить следующие:
-
Для вероятностных вычислений не известно хороших общих нижних оценок коммуникационной сложности даже для случая односторонних вычислений, как, например, в случае детерминированных вычислений.
-
До результатов автора не было установлено собственной иерархии сложности вероятностных вычислений по параметру надежности вычислений.
-
Не известно, почему для некоторых функций удается строить экономное по сравнению с детерминированным вероятностное вычисление, тогда как для других функций это сделать не удается.
Цель работы. Доказать общие нижние оценки односторонней вероятностной коммуникационной сложности булевых функций. Установить на основе доказанных нижних оценок сложности собственную иерархию классов вероятностной коммуникационной сложности. Применить полученные результаты для исследования сложности вычислений в вероятностных машинах. Распространить коммуникационные методы на исследование проблемы суперпозиции непрерывных функций и аппроксимации непрерывных функций.
Методы исследований. В работе используются методы дискретной математики, математической кибернетики, теории вероятностей и теории приближений.
Научная новизна. Все основные результаты диссертации являются новыми и имеют единый стержень — доказательства всех основных фактов используют коммуникационно-информационные идеи. Основными в диссертации являются следующие два результата.
I. Доказана нижняя оценка (энтропийная оценка) вероятностной односторонней коммуникационной сложности булевой функции. Эта оценка доказана в терминах детерминированной односторонней коммуникационной сложности булевой функции и величины коммуникационной структуры (введенной в работе) булевой функции. Для доказательства энтропийной оценки сложности предложен энтропийный методу в основе которого лежит энтропийный подход к доказательству нижней оценки сложности распознавания одного языка на вероятностной машине Тьюринга, предложенный Р.Фрейвалдом и И.Икауниексом в 1977 году.
Энтропийная оценка позволяет в ряде случаев объяснить, почему для некоторых, функций удается строить весьма экономное по сравнению с детерминированным вероятностное вычисление, тогда как для других функций это сделать не удается.
Из энтропийной оценки получен целый ряд следствий. В частно-
сти,
-
установлена иерархия сложности вероятностных коммуникационных вычислений по параметру надежности вероятностного вычисления булевых функций,
-
доказаны нижние оценки сложности распознавания языков на вероятностных машинах и как следствие установлена собственная иерархия классов вероятностной сложности в классе SPACE{n).
II. Методы коммуникационной сложности распространены на исследование классической проблемы суперпозиции непрерывных функций и сложности аппроксимации непрерывных функций. Введено понятие коммуникационной сложности дискретной аппроксимации непрерывных функций. Разработан коммуникационный метод, на основе которого
-
явным образом построена непрерывная функция, непредставимая в виде суперпозиции более простых (в определенном смысле) непрерывных функций;
-
построена гладкая функция, трудно аппроксимируемая в рассматриваемой коммуникационной модели.
Практическая и теоретическая ценность. Диссертация носит теоретический характер. Полученные результаты и разработанные методы могут найти применение при проектировании сложных управляющих систем, в теории сложности алгоритмов и вычислений, в теории функций и теории приближений.
Апробация работы. Результаты диссертации излагались на международных конференциях по теории вычислений серии MFCS (в 1986 г. в Чехословакии, в 1988 г. в Чехословакии, в 1989 г. в Польше), серии FCT (в 1987 г. в СССР), серии ICALP (в 1993 г. в Швеции), серии LFCS (в 1994 г. в Санкт-Петербурге); на Всесоюзных конференциях по теоретической кибернетике (в 1988 г. в Горьком, в 1993 г. был принят доклад на X международную конференцию );
на Всесоюзных семинарах по дискретной математике и ее приложениям (Москва 1984, 1987, 1993); на семинарах по теории сложности Рочестерского университета (США) в 1992; на семинарах по математической кибернетике МГУ, по теории сложности управляющих систем на механико-математическом факультете МГУ, на семинаре по теории сложности в МИАН РАН, на научных семинарах и ежегодных итоговых конференциях Казанского университета, а также на некоторых других конференциях, школах и семинарах.
Публикации. Список работ, опубликованных по. теме диссертации, приводится в конце автореферата.
Структура и объем работы. Диссертация состоит из введения, трех глав и списка литературы. Объем работы 149 страниц машинописи.