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

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

Первышев Константин Вячеславович ИЕРАРХИИ ПО ВРЕМЕНИ ДЛЯ НЕКОТОРЫХ КЛАССОВ ЭВРИСТИК, АЛГОРИТМОВ С ПОДСКАЗКОЙ, КРИПТОГРАФИЧЕСКИХ ПРИМИТИВОВ 05.13.17 — Теоретические основы информатики

АВТОРЕФЕРАТ

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

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

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

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

Официальные оппоненты: академик, доктор физ.-мат. наук Матиясевич Юрий Владимирович (ПОМИ РАН) профессор, доктор физ.-мат. наук Верещагин Николай Константинович (механико-математический факультет МГУ)

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

Защита состоится “26” февраля 2009 года в 15 часов 30 минут на за седании совета Д 212.232.51 по защите докторских и кандидатских дис сертаций при Санкт-Петербургском государственном университете по ад ресу: 198504, Санкт-Петербург, Старый Петергоф, Университетский пр.

28, ауд. 405.

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

199034, Санкт-Петербург, Университетская наб. 7/9.

Автореферат разослан “ ” января 2009 года.

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

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

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

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

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

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

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

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

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

Цели работы.

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

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

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

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

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

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

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

1. Доказано существование иерархии по времени для эвристических алгоритмов из вычислительных классов NP, MA и AM. Дано но вое доказательство иерархии по времени для эвристических алго ритмов из класса BPP.

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

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

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

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

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

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

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

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

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

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

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

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

Работы [13] и [15] опубликованы в изданиях, входящих в перечень ВАК.

Работа [11] опубликована в издании, входившем в перечень ВАК на мо мент публикации.

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

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

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

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

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

Здесь и далее мы рассматриваем многоленточные машины Тьюринга.

Определим сложностной класс NP, который соответствует недетер минированным алгоритмам. Язык L принадлежит классу NP, если суще ствует некоторая многоленточная машина Тьюринга M (x, w) и некий по лином p(n), такие что M (x, w) совершает не более p(|x|) шагов, а также w {0, 1}p(|x|) : M (x, w) = 1 (при x L) w {0, 1}p(|x|) : M (x, w) = 0 (при x L).

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

Язык L принадлежит классам BPP, RP или ZPP, если существует неко торая многоленточная машина Тьюринга M (x, r) и некий полином p(n), такие что M (x, r) совершает не более p(|x|) шагов, а также (при x L) (для BPP) Pr [ M (x, r) = 1 ] 2/ (при x L) Pr [ M (x, r) = 0 ] 2/ (при x L) (для RP) Pr [ M (x, r) = 1 ] 1/ (при x L) Pr [ M (x, r) = 0 ] = (для ZPP) Pr [ M (x, r) = 1 ] 1/ и Pr [ M (x, r) = 0 ] = 0 (при x L) Pr [ M (x, r) = 0 ] 1/ и Pr [ M (x, r) = 1 ] = 0 (при x L), где вероятность берется по случайной строке r, равномерно распреде ленной на множестве {0, 1}p(|x|). Машине M позволено выдавать ответы, отличные от 0 и 1. Это оказывется существенным при определении клас са ZPP.

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

Язык L принадлежит классам AM или MA, если существует некото рая многоленточная машина Тьюринга M (x, r, w) и некий полином p(n), такие что M (x, r, w) совершает не более p(|x|) шагов, а также (для AM) Pr w {0, 1}p(|x|) : M (x, r, w) = 1 2/3 (при x L) Pr w {0, 1}p(|x|) : M (x, r, w) = 0 2/3 (при x L) (для MA) w {0, 1}p(|x|) : Pr [ M (x, r, w) = 1 ] 2/3 (при x L) w {0, 1}p(|x|) : Pr [ M (x, r, w) = 0 ] 2/3 (при x L), где вероятность берется по случайной строке r, равномерно распреде ленной на множестве {0, 1}p(|x|).

В данных выше определениях мы требовали, чтобы функция p(n) яв лялась некоторым полиномом. Если вместо этого потребовать, чтобы функ ция p(n) была O(t(n)) для некоторой фиксированной функции t(n), то мы получим вычислительные классы DTime[t(n)],NTime[t(n)], BPTime[t(n)] и т. д. Эти классы содержат языки, которые распознаются за время O(t(n)) в соответствующих вычислительных моделях.

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

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

L : L BPP : n Pr n [L(x) = L (x)] 1 (n), heur1(n) BPP = x{0,1} где вероятность берется по случайному входу x, равномерно распреде ленному на множестве {0, 1}n.

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

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

Формально, определим класс языков, распознаваемых за полиноми алное время вероятностными алгоритмами с ограниченной двусторонней ошибкой, получающими один бит подсказки. Язык L принадлежит клас су BPP/1, если существует некоторая многоленточная машина Тьюринга M (x, r, a), последовательность однобитовых строк {an } и некий поли n= ном p(n), такие что M (x, r, a|x| ) совершает не более p(|x|) шагов, а также Pr M (x, r, a|x| ) = 1 2/3 (при x L) Pr M (x, r, a|x| ) = 0 2/3 (при x L) где вероятность берутся по случайной строке r, равномерно распреде ленным на множестве {0, 1}p(|x|).

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

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

Функция T : N N называется правильной, если ее значение, пред ставленное в единичной системе счисления строкой 1T (n), вычислимо за время O(n + T (n)).

Вероятностная машина Тьюринга A называется r(n)-успешным взлом щиком функции G, если для бесконечно многих n выполнено Pr A(G(x)) G1 (G(x)), r(n) где вероятность берется по строке x, равномерно распределенной на мно жестве {0, 1}n, и по случайным числам машины A.

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

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

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

формаль но описываются основные вычислительные модели;

объясняется разли чие между моделями синтаксическими и моделями семантическими.

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

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

доказываются важные свойства этого семейства. Дается само доказательство иерархии для недетерми нированных эвристических алгоритмов:

Теорема 3.2. Для любых положительных a и c, NP heur1/2+1/na NTime[nc ].

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

Теорема 3.3. Для любых положительных a и c, heur11/na BPP heur1/2+1/na BPTime[nc ].

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

Теорема 3.5. Для любых положительных a и c, heur11/na MA heur1/2+1/na MATime[nc ].

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

Теорема 3.7. Для любых положительных a и c, heur11/na AM heur1/2+1/na AMTime[nc ].

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

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

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

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

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

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

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

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

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

Тогда для любого k 1 существует функция G FPTime[n]/1, не имеющая r(n)-успешного взломщика, работающего время O(nk ), од нако имеющая r(n)-успешного взлщомщика, работающего время O( nk log n · r(n) · 3 (2n) ).

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

ЛИТЕРАТУРА [1] Hartmanis J., Stearns R. On the computational complexity of algo rithms // Transactions of the American Mathematical Society. — 1965. — Vol. 117. — Pp. 285–306.

[2] Cook S. 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 Sci ence. — 1983. — Pp. 327–333.

[5] Barak B. A probabilistic-time hierarchy theorem for “slightly non uniform” 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 poly nomial time // IEEE Symposium on Foundations of Computer Sci ence. — 2004. — Pp. 316–324.

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

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

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ [9] Pervyshev K. 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 cryp tographic 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 crypto graphic function inversion with advice // PDMI Preprints. — No. 20. — 2006. — 14 pp.

[12] van Melkebeek D., Pervyshev K. A generic time hierarchy for seman tic 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, no. 3. — Pp. 136–143.