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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

Первышев Константин Вячеславович

□□3452518

ИЕРАРХИИ ПО ВРЕМЕНИ ДЛЯ НЕКОТОРЫХ КЛАССОВ ЭВРИСТИК,

АЛГОРИТМОВ С ПОДСКАЗКОЙ, КРИПТОГРАФИЧЕСКИХ ПРИМИТИВОВ

05.13.17 — Теоретические основы информатики

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

^ I.1 ■ \

Санкт-Петербург — 2008

ггА

003452518

Работа выполнена на кафедре информатики математико-механического факультета Санкт-Петербургского государственного университета

Научный руководитель: доцент, кандидат физ.-мат. наук

Гирш Эдуард Алексеевич

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

Матиясевич Юрий Владимирович (ПОМИ РАН)

профессор, доктор физ.-мат. наук Верещагин Николай Константинович (механико-математический факультет МГУ)

Ведущая организация: Математический институт им. В.А. Стеклова

Российской академии наук

Защита состоится "27" ноября 2008 года в 16 часов 30 минут на заседании совета Д 212 232.51 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 198504, Санкт-Петербург, Старый Петергоф, Университетский пр. 28, ауд 405.

С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб. 7/9.

Автореферат разослан "7.%" октября 2008 года.

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

Мартыненко Б. К.

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

Актуальность темы. Вопрос о том, дает ли большее количество вычислительных ресурсов возможность решать более трудные задачи, способствовал развитию теоретической информатики в начале 60-х годов. В одной из самых первых работ по вычислительной теории сложности Ю. Хартманис и Р. Стирнс [1] доказали существование иерархии по времени для детерминированных алгоритмов: имеется некоторый язык, который может быть распознан неким детерминированным алгоритмом за время 0(пк+*), но не может быть распознан никаким детерминированным алгоритмом за меньшее время 0(пк). Иными словами, чуть большее количество времени позволяет решить некоторую более сложную задачу.

За детерминированными алгоритмами настал черед других вычислительных моделей. Так, в начале 70-х годов С. Кук [2] первым показал, что иерархия по времени существует и для недетерминированных алгоритмов. В последующей статье Дж. Сейферас, М. Фишер и А. Мейер [3] предложили альтернативное доказательство этой иерархии. Однако, классической стала работа [4], в которой С. Жак изобрел технику отложенной диагонализации.

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

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

В последних исследованиях предметом рассмотрения стали алгоритмы с подсказкой, которые являются промежуточным вариантом между машинами Тьюринга и вычислительными схемами. В серии работ [5,6,7], авторами которых являются Б. Барак, Л. Фортноу, Р. Сантанам и Л. Тре-висан, был получен следующий интересный результат. Иерархии по времени существуют для вероятностных алгоритмов с ограниченной двусто-

ронней ошибкой и одним битом подсказки. Напомним, что существование иерархии для подобных алгоритмов без подсказки является открытым вопросом. Также, было показано существование иерархии для вероятностных алгоритмов с односторонней ошибкой и одним битом подсказки. Последняя из этих статей ([7]) в качестве открытого вопроса указывает существование иерархии для алгоритмов с одним битом подсказки в других семантических моделях.

Фокус самых последних исследований, касающихся иерархий по времени, сместился с "классических" алгоритмов, которые обязаны правильно решать задачу на каждом из возможных входов, к алгоритмам эвристическим. Так, Л. Фортноу и Р. Сантанам [6] показали наличие иерархии по времени для вероятностных эвристических алгоритмов с двусторонней ошибкой (эвристики - эта такие алгоритмы, которые могут неверно обрабатывать некоторые входы). Подобный результат верен и для квантового аналога указанного класса эвристик. Недавний обзор тех же авторов [8] в качестве открытого оставляет вопрос о существовании иерархий для эвристик из других вычислительных моделей.

Цели работы.

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

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

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

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

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

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

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

Основные результаты.

1. Доказано существование иерархии по времени для эвристических алгоритмов из вычислительных классов ЫР, МА и АМ. Дано новое доказательство иерархии по времени для эвристических алгоритмов из класса ВРР.

2. Доказано существование иерархии по времени для алгоритмов с одним битом подсказки из вычислительного класса 7РР.

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

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

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

Апробация работы. Результаты диссертации докладывались на следующих семинарах, симпозиумах и конференциях:

1. Заседание Санкт-Петербургского математического общества;

2. Семинар по дискретной математике ПОМИ РАН;

3. Международная научная школа по информатике для аспирантов (Эстония, 2006);

4. Международный симпозиум по алгоритмам и теории вычислительной сложности (Москва, 2007);

5. Международный симпозиум по сложности булевых функций (Даг-штуль, Германия, 2006);

6. Международная конференция по теории вычислительной сложности (IEEE Computational Complexity Conference, Прага, Чехия, 2006 и Сан Диего, США, 2007).

Публикации. Основные результаты диссертации опубликованы в семи работах [9, 10, 11, 12, 13, 14, 15], перечисленных в конце автореферата. Работы [13] и [15] опубликованы в изданиях, входящих в перечень ВАК. Работа [11] опубликована в издании, входившем в перечень ВАК на момент публикации.

В работах [12, 13] Первышеву К. В. принадлежит результат о существовании иерархий по времени для алгоритмов с одним битом подсказки, принадлежащих произвольным вычислительным моделям, основанным на машинах Тьюринга (в частности, вероятностных). Совместно с Д. ван Мелкебеком дано упрощенное доказательство указанной теоремы, развивающее классический метод диагонализации. В работах [10, 11] Первышеву К. В. принадлежит доказательство иерархии легко вычислимых с одним битом подсказки функций по времени их обращения, а Григорьеву Д. Ю. и Гиршу Э. А. принадлежит аналогичный результат для языков.

Структура и объем работы. Диссертация состоит из введения и четырех глав. Нумерация разделов, формул, алгоритмов, процедур, примеров, лемм и теорем ведется отдельно для каждой главы. Текст диссертации изложен на 88 страницах (исключая список литературы). Список литературы содержит 28 наименований.

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

Определения и обозначения. Прежде всего приведем некоторые определения, необходимые для изложения содержания работы.

Начнем с определения тех классов вычислительной сложности, которые встречаются в формулировках доказываемых теорем. Напомним, что класс Р состоит из тех и только тех языков, которые распознаются детерминированными машинами Тьюринга за полиномиальное время. Здесь и далее мы рассматриваем многоленточные машины Тьюринга.

Определим сложностной класс NP, который соответствует недетерминированным алгоритмам. Язык L принадлежит классу NP, если существует некоторая многоленточная машина Тьюринга М(х, w) и некий полином р(п), такие что М{х, w) совершает не более р(|ж|) шагов, а также

3и)£{0,1}р(|х|) : М(х, w) = 1 (при х £ L) Vw € {0, l}*!1') : М(х, w) = 0 (при х £ L).

Определим сложностные классы ВРР, RP и ZPP, которые соответ-свтуют трем наиболее распространенным типам вероятностных алгоритмов — вероятностным алгоритмам с ограниченной двусторонней ошибкой (ВРР), с ограниченной односторонней ошибкой (RP) и без ошибки (ZPP).

Язык L принадлежит классам ВРР, RP или ZPP, если существует некоторая многоленточная машина Тьюринга М(х,г) и некий полином р(п), такие что М(х, г) совершает не более р(|ж|) шагов, а также

(для ВРР) Рг[М(х,г) = 1] > 2/3 (прихеЬ) Рт [М{х,г) = 0] > 2/3 (при x&L)

(для RP) Рг[М(х,г) = 1] > 1/2 (прижеЬ) Рг[М(я,г) = 0] = 1 (при х £ L)

(длягРР) Pr [ M(x,r) = 1] > 1/2

и Рт[М{х,г) =0] =0 (приже/,) Рг[М(х,г) = 0] > 1/2

и Рг [ М(х, г) = 1 ] = 0 (при x&L),

где вероятность берется по случайной строке г, равномерно распределенной на множестве {0, Машине М позволено выдавать ответы, отличные от 0 и 1. Это оказывется существенным при определении класса ZPP.

Определим сложностные классы АМ и МА, которые соответсвтуют двум наиболее распространенным типам однораундовых интерактивных протоколов — играм типа Артур-Мерлин (АМ) и играм типа Мерлин-Артур (М А).

Язык Ь принадлежит классам АМ или МА, если существует некоторая многоленточная машина Тьюринга М(х, г, ю) и некий полином р(п), такие что М(х, г, ю) совершает не более р(\х\) шагов, а также

(для АМ)

Рг Рг

Зю е {0,1}р(1х1) : М(х,г,ги) = 1

> 2/3 (при х е Ь)

> 2/3 (при х Ь)

(дляМА) Зги 6 {0, 1}р(1х1) : Рг[М(х, г, го) = 1] > 2/3 (при х 6 Ь) Уго 6 {0, г}^) : Рг [ М(х, г, ги) = 0 ] > 2/3 (при ж £ Ь),

где вероятность берется по случайной строке г, равномерно распределенной на множестве {0,1}р(М).

В данных выше определениях мы требовали, чтобы функция р(п) являлась некоторым полиномом. Если вместо этого потребовать, чтобы функция р(п) была 0(<(п)) для некоторой фиксированной функции ¿(п), то мы получим вычислительные классы 0Т!те[£(га)],1\1Т|те[4(п)], ВРТ1те[£(п)] и т. д. Эти классы содержат языки, которые распознаются за время 0(^п)) в соответствующих вычислительных моделях.

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

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

Ьеиг^млВРР = \Ь:ЗЬ' еВРР :Уп Рг Шх) = Ь'(х)\ > 1 - 6(п)\,

[_ хб{0,1}" J

где вероятность берется по случайному входу х, равномерно распределенному на множестве {0,1}™.

Аналогичным образом можно определить классы языков, распознаваемых эвристическими алгоритмами из других вычислительных моделей, а также классы языков, распознаваемых эвристическим алгоритмами за время 0(£(п)).

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

Формально, определим класс языков, распознаваемых за полиноми-алное время вероятностными алгоритмами с ограниченной двусторонней ошибкой, получающими один бит подсказки. Язык L принадлежит классу ВРР/1, если существует некоторая многоленточная машина Тьюринга М(х, г, а), последовательность однобитовых строк {ап}^=1 и некий полином р{п), такие что М(х, г, а^) совершает не болеер(|х|) шагов, а также

Pr [M(x,r,alx\) = 1] > 2/3 (при х е L) Pr [М(х,г,а]х]) =0] > 2/3 (при х <£ L)

где вероятность берутся по случайной строке г, равномерно распределенным на множестве {0, 1}р(М).

Если разрешить строкам ап иметь длину 1(п), где 1(п) есть некоторая фиксированная функция, то мы получим класс BPP/i(n) — класс языков, распознаваемых вероятностными алгоритмами с ограниченной двусторонней ошибкой, получающими подсказку длины 1(п).

Кроме того, можно определить классы языков, распознаваемых алгоритмами с подсказкой, принадлежащими другим вычислительным моделям, а также классы языков, распознаваемых алгоритмами с подсказкой, работающими время 0(t(n)).

Функция Т : N —> N называется правильной, если ее значение, представленное в единичной системе счисления строкой вычислимо за время 0(п + Т(п)).

Вероятностная машина Тьюринга А называется г (п)-успешным взломщиком функции G, если для бесконечно многих п выполнено

где вероятность берется по строке х, равномерно распределенной на множестве {0,1}", и по случайным числам машины А.

Класс FPTime[nfc]/l состоит из функций G : {0,1}* —► {0,1}*, вычислимых некоторой детерминированной машиной Тьюринга с одним битом подсказки за время 0(пк).

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

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

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

Вторая глава посвящена иерархиям по времени для эвристических алгоритмов. Строится семейство графов-миксеров, используемых при доказательстве иерархии по времени для эвристических алгоритмов из модели недетерминированных вычислений; доказываются важные свойства этого семейства. Дается само доказательство иерархии для недетерминированных эвристических алгоритмов:

Теорема 3.2. Для любых положительных а и с,

ЫР % Неиг1/2+1/„аЬтте[пс].

Дается альтернативное доказательство усиления ранее известной теоремы о существовании иерарахии для вероятностных эвристических алгоритмов с ограниченной двусторонней ошибкой:

Теорема 3.3. Для любых положительных а и с,

Иеиг^/гсаВРР % Иеиг1/2+1/паВРТ1 те[пс].

Доказывается теорема о существовании иерархии для эвристических алгоритмов из модели однораундовых игр типа Мерлин-Артур:

Теорема 3.5. Для любых положительных а и с,

Ьеиг1_1/„аМА ^ Ьеигх/г-н/паМАТ'тЦп0].

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

Теорема 3.7. Для любых положительных а и с,

heuri.j/n-AM heur^+i/naAMTimeln0].

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

Третья глава посвящена иерархиям по времени для алгоритмов с подсказкой. Доказывается иерархия по времени для не допускающих ошибок вероятностных алгоритмов с одним битом подсказки:

Теорема 4.1. Для любого положительного с, ZPP/1 2 ZPTime[nc]/l.

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

Следствие 4.1. Для любых положительных cud, где с < d, ZPTime[nd]/l ^ ZPTime[nc]/l.

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

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

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

Теорема 5.1. Предположим, что односторонние функции существуют, Рассмотрим произвольную функцию г(п) = тгр, где р > 0. Рассмотрим произвольную правильную функцию ((п), неубывающую и неограниченную.

Тогда для любого k > 1 существует функция G € FPTime[n]/l, не имеющая г{п)~успешного взломщика, работающего время 0(пк), однако имеющая г(п)-успешного взлщомщика, работающего время

0( nk log п ■ г{п) ■ С3(2п)).

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

ЛИТЕРАТУРА

[1] Hartmanis J., Stearns R. On the computational complexity of algorithms 11 Transactions of the American Mathematical Society.— 1965. — Vol. 117. — Pp. 285-306.

[2] CookS. A hierarchy for nondeterministic time complexity// Journal of Computer and System Sciences. — 1973. — Pp. 343-353.

[3] Seiferas J., Fischer M., Meyer A. Separating nondeterministic time complexity classes // Journal of the ACM.— 1978.— Vol. 25.— Pp. 146-167.

[4] Zak S. A Turing machine time hierarchy// Theoretical Computer Science. — 1983. — Pp. 327-333.

[5] Barak B. A probabilistic-time hierarchy theorem for "slightly nonuniform" algorithms // International Workshop on Randomization and Approximation Techniques in Computer Science.— LNCS, 2002.— Pp. 194-208.

[6] Fortnow L., Santhanam R. Hierarchy theorems for probabilistic polynomial time // IEEE Symposium on Foundations of Computer Science. — 2004. — Pp. 316-324.

[7] Fortnow L., Santhanam R„ Trevisan L. Hierarchies for semantic classes // ACM Symposium on Theory of Computing. — 2005. — Pp. 348— 355.

[8] Fortnow L., Santhanam R. Recent work on hierarchies for semantic classes // SIGACTNews. — 2006. — Vol. 37, no. 3.

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

[9] Pervysheu К. Time hierarchies for computations with a bit of advice // Electronic Colloquium on Computational Complexity. — No. 54. — 2005.— 13 pp.

[10] Grigoriev D„ Hirsch E. A., Pervyshev K. Time hierarchies for cryptographic function inversion with advice // Electronic Colloquium on Computational Complexity. — No. 76. — 2005. — 14 pp.

[11] Grigoriev D., Hirsch E. A., Pervyshev K. Time hierarchies for cryptographic function inversion with advice // PDMI Preprints. — No. 20. — 2006,— 14 pp.

[12] van Melkebeek D., Pervyshev K. A generic time hierarchy for semantic models with one bit of advice // IEEE Conference on Computational Complexity. — IEEE Computer Society, 2006. — Pp. 129-142.

[13] van Melkebeek D., Pervyshev K. A generic time hierarchy with one bit of advice// Computational Complexity. — 2007. — June. — Vol. 16, no. 2, — Pp. 139-179.

[14] Pervyshev K. On heuristic time hierarchies // IEEE Conference on Computational Complexity. — IEEE Computer Society, 2007. — June. — Pp. 347-358.

[15] Первышев К. Иерархии по времени для алгоритмов с одним битом подсказки // Вестник Санкт-Петербургского университета. — 2008. — Сер. 10, вып. 3. — Стр. 136—143.

Подписано к печати 13.10.08. Формат 60x90 'Л6. Бумага офсетная. Гарнитура Тайме. Печать ризографическая. Печ. л. 1,0. Тираж 100 экз. Заказ 4312

Отпечатано в Отделе оперативной полиграфии химического факультета СПбГУ 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 26 Тел.: (812) 428-4043,428-6919

1 Введение

1.1 Иерархии по времени для эвристических алгоритмов

1.1.1 Постановка задачи

1.1.2 Результаты.

1.2 Иерархии по времени для алгоритмов с подсказкой

1.2.1 Постановка задачи

1.2.2 Результаты.

1.3 Иерархии по времени для криптографических примитивов

1.3.1 Постановка задачи

1.3.2 Результаты.

1.4 Обзор литературы.

2 Предварительные сведения

2.1 Модели вычислений синтаксические и семантические

2.2 Примеры вычислительных моделей

2.2.1 Недетерминированные машины.

2.2.2 Вероятностные машины.

2.2.3 Однораундовые игры.

2.3 Эвристические алгоритмы

2.4 Алгоритмы с подсказкой

2.5 Метод отложенной диагонализации.

2.5.1 Нумерация вычислительных машин.

2.5.2 Доказательство иерархии для NP.

3 Иерархии по времени для эвристических алгоритмов

3.1 Конструкция одного семейства графов-миксеров.

3.1.1 Графы-расширители.

3.1.2 Лемма о перемешивании.

3.1.3 Графы-миксеры.

3.2 Иерархия для эвристик из NP

3.3 Иерархия для эвристик из ВРР.

3.4 Иерархия для эвристик из МА.

3.5 Некоторые обобщения

3.6 Открытые вопросы

4 Иерархии по времени для алгоритмов с подсказкой

4.1 Иерархия для алгоритмов из ZPP с подсказкой.

4.2 Уплотнение иерархии.

4.3 Некоторые обобщения

5 Иерархии по времени для криптографических примитивов

5.1 Односторонние функции

5.2 Одна лемма об односторонних функциях.

5.3 Иерархия функций по времени обращения

5.4 Доказательство иерархии.

5.5 Обобщения и открытые вопросы.

Вопрос о том, дает ли большее количество вычислительных ресурсов возможность решать более трудные задачи, способствовал развитию теоретической информатики в начале 60-х годов. В одной из самых первых работ по вычислительной теории сложности Ю. Хартманис и Р. Стирнс [16] доказали наличие иерархии детерминированных алгоритмов по времени: существует язык, который может быть распознан некоторым детерминированным алгоритмом за время 0(nfc+e), но не может быть распознан никаким детерминированным алгоритмом за время 0(пк). Иными словами, чуть большее количество времени в самом деле позволяет решать более сложные задачи.

За детерминированными алгоритмами настал черед других вычислительных моделей. Так, в начале 70-х годов С. Кук [7] первым показал, что иерархия по времени существует также и для недетерминированных алгоритмов. Несколькими годами позже, Дж. Сейферас, М. Фишер и А. Мей-ер [22] предложили альтернативное доказательство иерархии по времени для недетерминированных алгоритмов. Однако, классической стала работа [28], в которой С. Жак для доказательства этой иерархии применил технику, получившую в дальнейшем название "отложенная диаго-нализация". Отметим, что эта техника позволяет доказать иерархию по времени не только для недетерминированных машин, но и для практически любой иной синтаксической модели вычислений.

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

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

В последние годы предметом рассмотрения стали алгоритмы с подсказкой, являющиеся промежуточным вариантом между машинами Тьюринга и вычислительными схемами. В серии работ [5, 8, 10], авторами которых являются Б. Барак, JI. Фортноу, Р. Сантанам и JI. Тревисан, был получен следующий результат. Иерархия по времени существует для вероятностных алгоритмов с ограниченной двусторонней ошибкой, пользующихся одним битом подсказки (один и тот же бит подсказки ап дается вместе с каждым входом длины п). В тех же работах было показано существование иерархии для вероятностных алгоритмов с односторонней ошибкой и одним битом подсказки. Статья [10] в качестве открытого вопроса указывает существование иерархии для алгоритмов с одним битом подсказки в других семантических моделях, в частности, в модели вероятностных алгоритмов без ошибки.

Помимо алгоритмов с подсказкой, последние исследования затрагивают существование иерархии для эвристических алгоритмов. Эвристические алгоритмы — это такие алгоритмы, которые решают задачу правильно на большинстве входов, но могут ошибаться на небольшой доле входов. Л. Фортноу и Р. Сантанам в работе [8] показали наличие иерархии по времени для вероятностных эвристических алгоритмов с ограниченной двусторонней ошибкой. Аналогичный результат верен и для квантового аналога указанного класса эвристических алгоритмов.

В обзорной статье [9] те же авторы в качестве открытого оставляют вопрос о существовании иерархий для эвристических алгоритмов в прочих семантических моделях (например, для эвристик в модели однора-ундовых игр), а также в некоторых синтаксических моделях (таких как недетерминированные эвристические алгоритмы).

1. Левин . Универсальные Задачи Перебора // Проблемы Передачи Информации. — 1973. — Т. 9, № 3. — С. 265-266.

2. Algebraic methods for interactive proof systems / C. Lund, L. Fort-now, H. Karloff, N. Nisan // Journal of the ACM. — 1992. — Vol. 39, no. 4. — Pp. 859-868.

3. Almost-everywhere complexity hierarchies for nondeterministic time / E. AHender, R. Beigel, U. Hertrampf, S. Homer// Theoretical Computer Science. — 1993. — Vol. 115, no. 2. — Pp. 225-241.

4. Arora S., Safra S. Probabilistic checking of proofs: A new characterization of NP // Journal of ACM. — 1998. — Vol. 45, no. 1. — Pp. 70122.

5. Barak B. A probabilistic-time hierarchy theorem for "slightly nonuniform" algorithms // International Workshop on Randomization and Approximation Techniques in Computer Science. — LNCS, 2002. — Pp. 194-208.

6. Cai J.-I., Nerurkar A., Sivakumar D. Hardness and hierarchy theorems for probabilistic quasi-polynomial time // ACM Symposium onTheory of Computing. — 1999. — Pp. 726-735.

7. Cook S. A hierarchy for nondeterministic time complexity // Journal of Computer and System Sciences. — 1973. — Pp. 343—353.

8. Fortnow L., Santhanam R. Hierarchy theorems for probabilistic polynomial time // IEEE Symposium on Foundations of Computer Science. — 2004. — Pp. 316-324.

9. Fortnow Lv Santhanam R. Recent work on hierarchies for semantic classes // SIGACTNews. — 2006. — Vol. 37, no. 3.

10. Fortnow Lv Santhanam R., Trevisan L. Hierarchies for semantic classes // ACM Symposium on Theory of Computing. — 2005. — Pp. 348-355.

11. Gaber O., Galil Z. Explicit construction of linear size superconcen-trators // Journal of Computer and System Sciences. — 1981.— Vol. 22.

12. Goldreich O. Foundations of Cryptography: Volume 1, Basic Tools. — Cambridge University Press, 2001.

13. Goldreich O., Sudan M., Trevisan L. From logarithmic advice to single-bit advice // Electronic Colloquium on Computational Complexity, technical reports. — 2004. — 4 pp.

14. Goldreich O., Wigderson A. On pseudorandomness with respect to deterministic observers // Proceedings of the satellite workshops of the 27th ICALP. — 2000.

15. Grigoriev D., Hirsch E. A., Pervyshev K. Time hierarchies for cryptographic function inversion with advice // PDMI Preprints. — No. 20, — 2006,— 14 pp.

16. Hartmanis J., Stearns R. On the computational complexity of algorithms // Transactions of the American Mathematical Society. — 1965. — Vol. 117. — Pp. 285-306.

17. Hennie F., Stearns R. Two-tape simulation of multitape Turing machines//Journal of the ACM.— 1966. — Vol. 13.

18. Hoory S., Linial N., Wigderson A. Expander graphs and their applications // Bulletin of the American Mathematical Society. — 2006, — Vol.43.

19. Karpinski M., Verbeek R. Randomness, provability, and the separation of monte carlo time and space // Computation Theory and Logic / Ed. by E. Borger. — Springer, 1987. — Vol. 270 of LNCS. — Pp. 189207.

20. Pervyshev K. Time hierarchies for computations with a bit of advice // Electronic Colloquium on Computational Complexity. — No. 54. — 2005,— 13 pp.

21. Pervyshev K. On heuristic time hierarchies // IEEE Conference on Computational Complexity. — IEEE Computer Society, 2007. — Pp. 347-358.

22. Seiferas J., Fischer M., Meyer A. Separating nondeterministic time complexity classes // Journal of the ACM. — 1978. — Vol. 25. — Pp. 146-167.

23. Shamir A. IP = PSPACE // Journal of the ACM. — 1992. — Vol. 39, no. 4. — Pp. 869-877.

24. Trevisan L. List-decoding usingthe XOR lemma // IEEE Symposium on Foundations of Computer Science. — 2003. — Pp. 126—135.

25. Wilber R. Randomness and the density of hard problems // IEEE Symposium on Foundations of Computer Science. — 1983.

26. ZakS. A Turing machine time hierarchy// Theoretical Computer Science. — 1983. — Pp. 327-333.