WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 ||

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

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

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

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

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

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

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

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

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

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

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

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

Теорема 3.7. Для любых положительных a и c, a a heur1-1/n AM heur1/2+1/n 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 algorithms // 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 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 // 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 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, no. 3. — Pp. 136–143.

Pages:     | 1 ||






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»