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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В.ЛОМОНОСОВА

Р Г Б ОД

На правах рукописи УДК 517.5, 519.95

Аблаев Фарид Мансурович

Коммуникационная сложность вероятностных вычислений и некоторые ее приложения

Специальность: 01.01.09 — математическая кибернетика

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

Москва - 1994

Работа выполнена на факультете вычислительной математики и кибернетики Казанского государственного университета

Официальные оппоненты: доктор физико-математических наук,

профессор Н.К.Косовский, доктор физико-математических наук, профессор М.И.Кратко, доктор физико-математических паук, профессор В.М.Тихомиров

Ведущая организация — Институт математики Сибирского

отделения РАН

Защита диссертации состоится в 16 час. 05 мин. на заседании специализированного Совета Л.053.05.05 при Московском государственном университете им. М.В.Ломоносова по адресу:

119899, ГСП, Москва, Ленинские Горы, МГУ, механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан

# ЖШЗЛ^ 199 ^г.

Ученый секретарь специализированного

Совета Д.053.05.05 при МГУ

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

профессор В.Н.Чубари*

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

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

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

В связи с этим очень важным является анализ, систематизация >езультатов и наработанных методов теории сложности. Введете в конце семидесятых годов в изучение коммуникационной вычи-лительной модели явилось результатом обобщения и осмысления оммуникационно-информационных ¡методов в доказательстве ниж-:их оценок сложности.

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

'Исследования по теме диссертации частично финансировались рантами УР-11/93 (Совр. проблемы мат. и мех.). РФФИ 94-01-00117, N3? ССГ?-8957604

Я.М.Барздиня в 1965 году. Метод следов и его обобщение — мето перекрытий — за последние десятилетия применялся для доказатель ства нижних оценок времени и памяти вычислений на многоленточ пых и вероятностных машинах Тьюринга.

Схемные вычислительные модели являются более "тонким инструментом" при исследовании еложностных аспектов вычислений чем вычислительные модели с памятью. Это, в частности, выражается в более разнообразном проявлении коммуникационно-информационных методов доказательств нижних оценок сложности в схемных модельных классах, чем в вычислительных моделях с памятью. Например, коммуникационный подход лежит в основе метода В.М.Храпченко доказательства нижних оценок сложности в классе П-схем. Явным образом коммуникационной подход достаточно хорошо работает для доказательства нижних оценок сложности реализации функций в схемах из клеточных элементов. В последние годь коммуникационный метод успешно применялся различными автора ми для доказательства нижних оценок сложности в схемах из поро говых элементов ограниченной глубины. По-видимому, возможное!! коммуникационных методов в теории схемной сложности далеко не исчерпаны.

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

Общепринятая абстрактная модель, ориентированная на изуче ние коммуникационной сложности для детерминированных и вероят ностных вычислений, была введена Яо в 1979 году. Содержатель» коммуникационная вычислительная модель может быть описана еле дующим образом. Имеется два вычислителя и линия связи между ни

ми, по которой они могут обмениваться последовательностями двоичных сигналов. Каждый из вычислителей получает свою часть входной информации, и они хотят совместно вычислить число, которое является функцией от обоих входов. Предполагается, что 1) оба вычислителя имеют неограниченные вычислительные возможности и 2) вычисления в самих вычислителях "ничего не стоят". Однако каждый пересылаемый бит между вычислителями имеет "стоимость". Обмен информацией (двоичными последовательностями) продолжается до тех пор пока один из вычислителей не,будет готов дать ответ.

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

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

В диссертации рассматривается коммуникационное вычисление булевых функций. Булева функция /:1хУ-»{0,1}в общем случае вычисляется следующим образом: последовательность х € X подается на вход вычислителя Рь а последовательность у 6 У — на вход вычислителя Р2. Вычислитель Р] первым начинает передавать информацию. После необходимого обмена информацией между вычислителями вычислитель Р2 выдает знаЧёние функции /(х,у).

Детерминированная коммуникационная сложность ОС(/) булевой функции / — это ппп тах{С^}, где максимум берется по всем парам (х, у) £ X х У, а минимум — по всем детерминированным протоколам, вычисляющим функцию /.

Вероятностная коммуникационная сложность РСр(/) булевой функции / — это гшптах{Сф}, где максимум берется по всем парам

(ж>!/) € X х Y, а минимум по всем вероятностным протоколам, вычисляющим функцию / с вероятностью не меньше, чем р, р> 1/2.

Теория нижних оценок коммуникационной сложности вычислений переживает в последнее десятилетие свое бурное развитие. Исследования по нижним оценкам коммуникационной сложности булевых функций начались с момента определения коммуникационной модели вычислений. В последние годы в англоязычной литературе появились обзоры по коммуникационной сложности вычислений и приложений коммуникационных методов в различных областях теории сложности и СБИС теории2.

Известные общие нижние оценки коммуникационной сложности основаны на анализе коммуникационной матрицы булевой функции. Булевой функции f с выбранным разбиением Х,У входов естественным образом соответствует коммуникационная матрица СМ/, строки котораК соответствуют входам изХ, а столбцы — входам изУ. На пересечении строких £ X и столбцау € У стоит значение f(x,y).

Для одностронних коммуникационных вычислений (только вычислитель Р\ передает сообщение вычислителю выполняется

DC(f) = \nrow(CMf)].

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

• Алгебраический подход, предложенный в работе К.Мельхорна и Е.Шмидта. Для детерминированных коммуникационных вы-

2см., например, обзор Л.Ловаза (Lovasz L.) Communication Complexity: A Survey в сборнике. "Patlis, Flows and VLSI Layout", Korte, Lovasz, Promel, Schrijver Eds., Springer-Verlag 1990, p. 235-266; и обзор Т.Ленгауэра (Lengauer Т.) VLSI Theory в сборнике Handbook of Theoretical Computer Science, Edited by J. van Leeuwen, Elsevier Science Publishers В. V. 1990, p. 837-868.

числений в терминах ранга коммуникационной матрицы СМ начиная с работы К.Мельхорна и Е.Шмидта, были доказаны разные варианты нижних оценок комм^ЕникационноЙ сложности.

• Для недетерминированных коммуникационных вычислений в терминах логарифма числа покрытий коммуникационной матрицы СМ монохромными подматрицами (Р.Липтон).

Для вероятностных коммуникационных вычислительных моделей имеются определенные достижения в доказательстве нижних оценок сложности как для почти всех булевых функций (А.Яо и др.), так и для некоторых индивидуальных функций. Наиболее высокие нижние оценки вероятностной и недетерминированной коммуникационной сложности для ряда индивидуальных естественных функций доказаны в работах А.А.Разборова.

В качестве открытых вопросов теории коммуникационной сложности и теории сложности вероятностных вычислений можно отметить следующие:

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

2. До результатов автора не было установлено собственной иерархии сложности вероятностных вычислений по параметру надежности вычислений.

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

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

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

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

I. Доказана нижняя оценка (энтропийная оценка) вероятностной односторонней коммуникационной сложности булевой функции. Эта оценка доказана в терминах детерминированной односторонней коммуникационной сложности булевой функции и величины коммуникационной структуры (введенной в работе) булевой функции. Для доказательства энтропийной оценки сложности предложен энтропийный методу в основе которого лежит энтропийный подход к доказательству нижней оценки сложности распознавания одного языка на вероятностной машине Тьюринга, предложенный Р.Фрейвалдом и И.Икауниексом в 1977 году.

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

Из энтропийной оценки получен целый ряд следствий. В частно-

сти,

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

2) доказаны нижние оценки сложности распознавания языков на вероятностных машинах и как следствие установлена собственная иерархия классов вероятностной сложности в классе SPACE{n).

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

1) явным образом построена непрерывная функция, непредставимая в виде суперпозиции более простых (в определенном смысле) непрерывных функций;

2) построена гладкая функция, трудно аппроксимируемая в рассматриваемой коммуникационной модели.

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

Апробация работы. Результаты диссертации излагались на международных конференциях по теории вычислений серии MFCS (в 1986 г. в Чехословакии, в 1988 г. в Чехословакии, в 1989 г. в Польше), серии FCT (в 1987 г. в СССР), серии ICALP (в 1993 г. в Швеции), серии LFCS (в 1994 г. в Санкт-Петербурге); на Всесоюзных конференциях по теоретической кибернетике (в 1988 г. в Горьком, в 1993 с был принят доклад на X международную конференцию );

на Всесоюзных семинарах по дискретной математике и ее приложениям (Москва 1984, 1987, 1993); на семинарах по теории сложности Рочестерского университета (США) в 1992; на семинарах по математической кибернетике МГУ, по теории сложности управляющих систем на механико-математическом факультете МГУ, на семинаре по теории сложности в МИАН РАН, на научных семинарах и ежегодных итоговых конференциях Казанского университета, а также на некоторых других конференциях, школах и семинарах.

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

Структура и объем работы. Диссертация состоит из введения, трех глав и списка литературы. Объем работы 149 страниц машинописи.

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

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

Каждая глава начинается с параграфа "Предварительные сведения". В них излагается краткая история вопроса и дается обзор основных известных результатов.

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

является энтропийная нижняя оценка коммуникационнои сложности.

Данная диссертация — это, по-видимому, первая работа, в которой рассматривается "тестовая характеристика" коммуникационных матриц и устанавливается связь мощности теста коммуникационной матрицы булевой функции с ее коммуникационной сложностью. Понятие теста таблицы было введено С.В.Яблонским в пятидесятых годах и хорошо известно в кибернетике. Тест таблицы М — это подмножество ее столбцов, которые позволяют различать все попарно различные строки таблицы М. Вероятностная коммуникационная характеристика рсср{$) функции / определяется соотношением

**(/) = Г-^ЩггМр),

где ts(CMf) — мощность минимального теста матрицы СМ/, пгои>(СМу) — число попарно различных строк коммуникационной матрицы СМ/, а Н(р) — шенноновская энтропия. Вероятностная коммуникационная характеристика, основанная на соотношении мощности минимального теста и числа попарно различных строк коммуникационной матрицы, является характеристикой внутренней структуры булевой функции.

Энтропийная нижняя оценка коммуникационной сложности РСр(/) для одностороннего вероятностного коммуникационного вычисления произвольной булевой функции / : {0,1}" х {0,1}" —► {0,1} с вероятностью р доказывается в первой главе и имеет следующий вид (теорема 1.2):

Теорема 1.2 (Энтропийная оценка) Для произвольной булевой функции / : {0,1}" X {0,1}п -+ {0,1}, для произвольного £ 6. (0,1/2], р = ^ + е выполняется

РСр(/) > £>С(/)(1 - рсср(/)) - 1.

Здесь £>С(/) — детерминированная односторонняя коммуникационная сложность, функции /.

Так как flog nrow(CA//)] < ts{CMj) < nrow(CMf), то чем "гуще" матрица СМ/, тем меньше значение вероятностной коммуникационной характеристики pccp(f) матрицы СМ/ и, следовательно, выше нижняя оценка вероятностной коммуникационной сложности. Эти соображения дают качественное объяснение, почему для одних булевых функций удается строить надежные и экономные по сравнению с детерминированными вероятностные коммуникационные вычисления, а для j других функций таких экономных вероятностных вычислений нет.

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

В качестве примера влияния коммуникационной структуры булевой функции на величину ее вероятностной коммуникационной сложности в первой главе приводится пример двух функций fi(x,y) и /|(х,7/), которые демонстрируют неожиданный факт. Детерминиро-ванно функция }'{(х, у) сложнее функции Д(х,у), а вероятностно, наоборот, функция /|(а;,?/) сложнее функции у). Этот экзотический факт объясняется влиянием коммуникационной характеристики функции на величину вероятностной коммуникационной сложности.

В заключительном параграфе перввц главы в качестве следствия энтропийной оценки и того, что для почти всех функций / : {0,1}" х {0,1}" —► {0,1} выполняется ts(CM(f) = ("lognrow(CMf)], приводится нижняя оценка вероятностной коммуникационной сложности почти всех функций. Нижняя оценка вероятностной коммуникационно! сложности почти всех функций для фиксированной величины надежности вероятностного коммуникационного вычисления была устано

влена Яо и далее исследовалась целым рядом авторов для различных моделей вероятностных коммуникационных моделей. Наша оценка улучшает оценку Яо для случая вероятностного коммуникационного вычисления с увеличивающейся (в зависимости от арности функции) величиной надежности вычисления.

Во второй главе коммуникационные методы исследований распространяются на исследование проблемы суперпозиции и сложности аппроксимации непрерывных функций! Проблема представления непрерывной функции в виде суперпозиции непрерывных функций более простого (в некотором смысле) вида восходит к задаче представления решения общего уравнения ахХп+а2Хг'~1 + ■ • •+ап^+ап+1 = 0 как функции коэффициентов. Современные исследования в этой области были инициированы 13-ой проблемой Гильберта.

Для класса р раз непрерывно дифференцируемых функций от к переменных А.Г. Витушкин доказал, что в классе У7* существует функция, не представимая в виде суперпозиции функций из если только ^ > д- Позже А.Н. Колмогоров дал доказательство теоремы Витушкина, основанное на сравнении сложностных характеристик (энтропии) множеств функций из пространств Т^ и Необходимо подчеркнуть, что доказательства Витушкина и Колмогорова показывают только существование таких функций.

Существенный шаг в направлении явного построения непрерывной функции из класса не представимой в виде суперпозиции функций худшего качества, сделал С.С. Марченков. Он предложил метод задания непрерывной функции на основе сложно реализуемых (в схемном смысле) булевых функций. Как доказал С.С. Марченков сложно реализуемые булевы функции определяют непрерывную функцию из класса У-*, которая не представима в виде суперпозиции функций из Тьч, если только ^ > Задача построения сложно реализуемой функции решается перебором. Но проблема построения индивидуальных сложно реализуемых булевых функций в настоящее время

остается открытой.

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

Функция fU}g от к переменных, определяемая в кубиках I^ — I tiT+T'inr]4 кУба [О, l]fc, строится с использованием соответствующей конструкции Колмогорова-Тихомирова:

м*)= Е j^w-^H)®«,«.)(*), (o.i)i

где Ф„ь(„)(х) — простые линейные функции, задаваемые в кубиках I*, ш(6(п)) — модуль непрерывности, а gn{v) — булева функция от п переменных, задаваемая формулой

k [log п"1

9n{v)= V Л У? Axord(<r),

V, ¡=1

0<ord(<r)<fc(n—[lag n"l)

гДе Vj (xj) это j-ый символ последовательности v в общей нумерации ее элементов, ord{a) — натуральное число, двоичное разложение которого есть о.

Пусть А', В3 — некоторые классы непрерывных функций соответственно от t и s переменных.

Обозначим SHASB*]

— класс непрерывных функций от к переменных, представимых суперпозициями ви да F (Л^а:},..., я}),..., ■••,*<))> гДе это функция и:

В% а {к{{х u...,xt) : 1 <i<s } С А4.

Обозначим класс всех равномерно непрерывных функций от ) переменных, модуль непрерывности которых не превышает по поряд ку заданного модуля непрерывности и>(6). Непосредственно из опре деления следует, что для модулей непрерывности Wi(6), ^2(6) функ

ция uj(8) = w2(wi (¿)) является модулем непрерывности и Spk[H[lx, ] С

Обозначим множество функций из класса со свойством: для всех функций / € Для всех 6 вида 8 = 8(п) — (п+'1)2„ модуль непрерывности ы/(8(п)) функций / равен ш(6(п)) с точностью до мультипликативной константы.

Функция fUi9 принадлежит классу

Теорема о суперпозиции Пусть u>i((5) такая строго возрастающая с ростом 6 функция, что не возрастает с ростом 6 и

Тогда для я > 1, для М > 0,7 е (0,1], для ш2{6) = М8~>, ш(8) = ш2{и>1(8)) функция/ш<д(х) принадлежит классу'Н£1\Зрк['Н1п,Н^}2].

Заметим, что функции, модуль непрерывности которых удовлетворяет условию (0.2) теоремы о суперпозиции, не входят в класс Гельдера И* = и7б(о,1]^7. Но, например, класс 7{Шр для р > 1, где

„(5) = {

[ (Ы/а)Р-

если 0 < х < а если х > а,

а = 1/(ер+1) таков, что модуль непрерывности и>р(8) удовлетворяет условиям теоремы о суперпозиции для модуля непрерывности (8). Класс ЛЫг входит в класс Дини

D = |/:limc,;(5)logi = o}.

Следствие 0.1 Функция /ир,д(х) от к > 4 переменных входит в класс и не представима в виде суперпозиции функций от £ переменных из класса 'Н* на первом уровне суперпозиции и функций из класса ~Н\ на последующих уровнях, если t < к.

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

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

Мы используем стандартное определение вероятностного автомата и традиционное определение Рабина представления языка в вероятностном автомате. Для языка Ь £ Е* обозначим РР(Ь) наименьшее из возможных чисел состояний вероятностного автомата, представляющего язык Ь с вероятностью не меньше = | +£, £ > 0. Построена последовательность конечных языков Ьк, для которой справедливо следующее утверждение.

Теорема, Для произвольного е € (0, для р = | + е, начиная с некоторого к = к(е), выполняется

(оп\1 -Мр) /о

т) * ■

где ^(е) = | - ¿рт, Цр) = (1 -р)1оё(1 -р).

На основе доказанной теоремы установлена иерархия вероятностной сложности языков по параметру надежности вероятностного распознавания:

• В полуинтервале (0, существует бесконечная последовательность чисел £] < £2 < £з < . • • такая, что для всех г > 1, pi = | +

при * —

Для исследования емкостной сложности (сложности памяти) распознавания языков на машинах Тьюринга достаточно рассматривать двухленточную модель машины. Исходное слово в алфавите £ записывается па первой ленте, которая называется лентой ввода (входной лентой). На ленте ввода располагается читающая (только) головка, которая может читать (но не может писать), может стоять на месте i или двигаться слева направо (но не может двигаться справа налево). На второй (рабочей) ленте располагается рабочая головка, которая может читать, писать и двигаться в обоих направлениях.

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

Говорят, что вероятностная машина М распознает язык L CS* с вероятностьюр, р > 1/2, с памятью S(n\ если М при работе на любом слове v £ Е* с вероятностью не меньше, чем р, выдает результат 1 (0), если v € L (v ^ L). При этом любой вариант обработки слова v, завершающийся остановом машины М, использует не более S(n) ячеек памяти на рабочей ленте.

Для вероятностной машины М, распознающей язык L СЕ'с вероятностью р, р > 1/2, с памятью S(n), для функции 1(п) будем писать

•V

S(n) t ¡(n),

если существует такая константа с > 0, что для бесконечно многих п выполняется S(n) > с/(п).

Обозначим paí(n) разбиение слов из Е" на начала и окончания так, что все начала имеют одинаковую длину. Для языка L, числа п обо-

значим DC(L,pat(n)) детерминированную коммуникационную ело. ность характеристической функции Д „ : Е" —> {0,1} языка £ Л £" дл. коммуникационного вычисления с разбиением pat(n) входных после довательностей из S".

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

Теорема (Энтропийная оценка) Пусть язык L С Е*, р-распозна ется вероятностной машиной Тьюринга М. Пусть е € (0, = j+q Тогда для произвольного разбиения pat(n) слов из £" выполняется

5M(n) h DC(L,pat(n))(l — pccp(L,pat(n))).

Теорема (Топологическая оценка) Пусть языкЬ С £*, р-распо: нается вероятностной машиной Тьюринга М. Пусть е € (0, р : Тогда для произвольного разбиенияpat(n) слов из S" выполняете

SM(n) У logDC{L,pat(n)) - loglog(l + l/e).

Обозначим 1£)5'РЛС-Е'(5(п)) класс языков, распознаваемых одн< сторонними детерминированными машинами Тьюринга (сокращена 1DTM) с ленточной сложностью по порядку не более S(n). Обозн; чим lBPSPACE(S(n),p) класс языков, распознаваемых односторо] ними вероятностными машинами Тьюринга (сокращенно \РТМ) с в роятностью р > 1/2, с ленточной сложностью по порядку не бол« £(гс). Говорят, что функция S(n) абсолютно односторонне констр; ируема, если существует такая детерминированная односторонне машина Тьюринга М, которая при обработке любого слова длины обязательно останавливается и использует ровно 5(п) ячеек рабоч< ленты.

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

Для абсолютно односторонне конструируемых функций 5(n), S'(n) :аких, что logn ^S(n), S(n) = o(S'(n)), S'(n) < n, для e e (0,1/2] зыполняется:

I

1. lBPSPACE(S(n), 1/2 + e) С lBPSPACE(S'(n), 1/2 + e),

2. 1 DSPACE(S(n)) С lBPSPACE(S(n), 1/2 + e),

I

3. íDSPACE(S'(n)) (JL lBPSPACE(S(n), 1/2 + e).

4. Для S'(n) -< n выполняется:.

1 BPSPACE(S(n), 1/2 + e) £ lDSPACE(ff(n)).

5. Для i > 1, t = 2', e,(n) = l/0(n2^) выполняется: 15Р5РЛС^(п1-,/£',l/2+£i+3(n)) С lBPSPAC^n1-1^,l/2+e,(n)).

Автор признателен Ю.В.Голункову и Н.З.Габбасову за прочтение текста диссертации и за полезные замечания:

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Аблаев Ф.М- Возможности вероятностных машин по предста-леншо языков в реальное время. — Известия вузов, Математика, 985, вып. 7, с. 32-40.

2. Аблаев Ф.М. Влияние степени изолированности точки сечения а число состояний вероятностного автомата. — Математические аметки, 1988, т.44. вып. 3, с. 289-297.

3. Аблаев Ф.М. Сравнительная сложность представления языков вероятностных автоматах. — Кибернетика, 1989, с. 21-26.

4. Аблаев Ф.М. О сравнительной сложности вероятностных и детерминированных автоматов. — Дискретная математика, 1991, т. 3, вып. 2, с. 114-120.

5. Аблаев Ф.М. Нижние оценки для вероятностной односторонней коммуникационной сложности булевых функций. — Тезисы докладов Х-ой международной конференции по проблемам теоретической кибернетики. В сборнике: Методы и системы технической диагностики. — Саратовский университет, 1993, вып. 18, с. 3.

6. Аблаев Ф.М. Коммуникационный метод анализа суперпозиции непрерывных функций. — Тезисы докладов международной научной конференции АЛГЕБРА И АНАЛИЗ, часть II. — Казань, 1994, с. 5-7.

7. Ablayev F. Possibilities of probabilistic one-way counting machines. — in Proc. of the FCT'87, Lecture Notes in Computer Science, 1987, 278, p. 1-4.

8. Ablayev F. The complexity properties of probabilistic automata with isolated cut point. — Theoretical Computer Science, 1988, 57, p. 87-95.

9. Ablayev F. On Comparing Probabilistic and Deterministic Automata Complexity of Languages. — in Proc. of the MFCS'89, Lecture Notes ir Computer Science, 1989, v. 379, p. 599-605.

10. Alayev F. Lower bounds for one-way probabilistic communicatioi complexity. — in Proc. of the ICALP'93, Lecture Notes in Compute] Science, 1993, v. 700, p. 241-252.

11. Alayev F. Lower bounds for probabilistic space complexity: commu nication-automata approach. — in Proc. of the LFCS'94, Lecture Notes ii Computer Science, 1994, v. 813, p. 1-7.