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

Вопрос о том, дает ли большее количество вычислительных ресурсов возможность решать более трудные задачи, способствовал развитию теоретической информатики в начале 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. 70 122.

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. 189 207.

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.