Структурная теория сложности

Структурная теория сложности

Структурная теория сложности имеет дело не с конкретными алгоритмическими задачами, а с целыми классами задач, которые объединяются в зависимости от моделей вычислений и необходимых для решения этих задач ресурсов. Основной задачей структурной теории сложности является изучение взаимоотношения между этими классами. Многие классы содержат “типичные” (самые сложные в этом классе) задачи, отражающие свойства целого класса: так, например, чтобы решить известную задачу о равенстве классов P и NP (одну из “проблем тысячелетия”), достаточно выяснить, существует ли полиномиальный по времени алгоритм для конкретной задачи - распознавания тавтологий логики высказываний. 

Важной задачей в структурной теории сложности является построение иерархий, которые являются основным инструментом для доказательства различия классов сложности. Например, иерархия по времени утверждает, что за большее время можно решить большее количество задач. Иерархия по времени известна для детерминированных вычислений, но является открытым вопросом для алгоритмов, использующих случайные числа.
Структурная теория сложности изучает фундаментальные факты о сложности задач, и, таким образом, является базой для любых рассуждений о вычислительной сложности - от эффективности работы алгоритмов до надёжности криптосистем. Хотя до сих пор на многие естественные вопросы ответ еще не получен, известно внушительное количество неожиданных соотношений между сложностными классами: например, теорема Шамира утверждает, что для каждой задачи, решаемой с полиномиальной памятью, существует интерактивный протокол, теорема Савича показывает, что  недетерминированные вычисления моделируются детерминированными вычислениями лишь с квадратным увеличением памяти, PCP-теорема говорит, что выполняющий набор для булевой формулы (равно как и любой сертификат для NP-задачи) можно переписать таким образом, чтобы его можно было проверить, прочитав только константное число его битов.

 

Сотрудники кафедры: 

Э.А.ГиршД.М.ИцыксонА.А.КнопД.О.Соколов

 

Публикации сотрудников кафедры

  1. E. A. Hirsch, D. Sokolov. On the probabilistic closure of the loose unambiguous hierarchy. Information Processing Letters 115(2015):725-730
  2. D. Grigoriev, E. A. Hirsch, K. Pervyshev, Time hierarchies for cryptographic function inversion with advice. ECCC Report TR05-076. Русская версия: Записки научных семинаров ПОМИ 358(2008): 54-76.
  3. D. Itsykson, Structural complexity of AvgBPP. Annals of Pure and Applied Logic, 162(3): 213-223, 2010.
  4. А. А. Кноп, Диофантова иерархия. Записки научных семинаров ПОМИ 399(2012):109-127, 2012.
  5. A. Knop, Circuit Lower Bounds for Average-Case MA. Proceedings of CSR 2015.
  6. D. Itsykson, A. Knop, D. Sokolov. Complexity of distributions and average-case hardness. ECCC Report TR15-174.
  7. D. Itsykson, A. Knop and D. Sokolov. Heuristic time hierarchies via hierarchies for sampling distributions. Proceedings of ISAAC 2015.

Квалификационные работы

  1. Ф. А. Парт. Недетерминированные вычисления, полиномиальные в среднем. Магистерская диссертация, СПбАУ РАН, 2011.
  2. Д. М. Ицыксон. Сложность в среднем случае вероятностных вычислений с ограниченной ошибкой. Диссертация на соискание степени кандидата физико-математических наук. ПОМИ РАН, 2009.