Иерархии по времени для некоторых классов эвристик, алгоритмов с подсказкой, криптографических примитивов тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Первышев, Константин Вячеславович

• Первышев, Константин Вячеславович
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Первышев, Константин Вячеславович

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] те же авторы в качестве открытого оставляют вопрос о существовании иерархий для эвристических алгоритмов в прочих семантических моделях (например, для эвристик в модели однора-ундовых игр), а также в некоторых синтаксических моделях (таких как недетерминированные эвристические алгоритмы).

Список литературы диссертационного исследования кандидат физико-математических наук Первышев, Константин Вячеславович, 2007 год

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.