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

Программа экзамена

  1. Задачи поиска и распознавания. Детерминированная и недетерминированная машины Тьюринга. Класс P. Три определения класса NP. Сводимости по Карпу и по Левину. Полные задачи.
  2. NP-полнота BH, Circuit SAT и 3-SAT.
  3. Эквивалентность задач поиска и распознавания для NP-полных языков.
  4. Левинский оптимальный алгоритм для NP-задач поиска.
  5. (*) Пропозициональные системы доказательств. NP vs coNP. Оптимальные аксепторы и оптимальные системы доказательств (эквивалентность существования).
  6. Задачи в NP, не являющиеся NP-полными и не принадлежащие P.
  7. Полиномиальная иерархия: два определения (с эквивалентностью), полные задачи, условия коллапса.
  8. Теорема Карпа-Липтона.
  9. Схемная сложность Σ2.
  10. PSPACE-полнота QBF.
  11. RP, BPP, ZPP, PP. NP ⊆ PP. Лемма Шварца-Циппеля. Вероятностное выяснение тривиальности полинома.
  12. (**) Уменьшение вероятности ошибки в BPP: обычное и эффективное по количеству случайных битов.
  13. BPP ⊆ P/poly.
  14. Иерархии DTime, NTime, DSpace.
  15. Достижимость в ориентированном графе в DSpace[(log n)2], NSpace[f(n)] ⊆ DSpace[f(n)2].
  16. (**) NSpace[f(n)] ⊆ coNSpace[f(n)].
  17. NC, сводимости, P-полные задачи, следствия из их принадлежности DSpace[log n] и NC.
  18. (**) Параллельные вычисления. Параллельные алгоритмы для сложения и умножения чисел; для умножения матриц.
  19. NC1 vs DSpace[log n] vs NSpace[log n] vs NC2.
  20. IP, протокол для неизоморфизма графов, IP=PSPACE (с экономией коммуникации).
  21. Классы MA и AM с односторонней и двусторонней ошибкой. Параллельное уменьшение ошибки в протоколах с одним прувером. MA⊆AM.
  22. \exists BPP⊆NPBPP⊆MA=MA2⊆ZPPNP⊆Σ2.
  23. ParityP, замкнутость относительно дополнения и использования оракула.
  24. Лемма Вэлианта-Вазирани и её релятивизованный вариант.
  25. BPPBPPA = BPPA, ParityPBPPA ⊆ BPPParityPA и первая часть теоремы Тода.
  26. PP, #P. Вторая часть теоремы Тода.
  27. Интерактивный протокол для перманента. Схемная сложность PP.
  28. AM[k]=AM[2] ( (**) версия с уменьшением произвольного количества раундов вдвое).
  29. (**) Протокол Гольдвассер-Сипсера: IP[f(n)]⊆ AM[f(n)+2].
  30. MIP=NEXP.
  31. Первая часть PCP-теоремы. Связь с неаппроксимируемостью.

Продолжение курса

Основная литература

  • Arora, Barak, Computational Complexity: A Modern Approach. CUP, 2009.
  • Christos H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
  • Конспекты лекций похожего курса.
  • Goldwasser, Sipser, Public coins versus public coins in interactive proof systems, STOC86.
  • Babai, Moran. Arthur-Merlin Games: A Randomized Proof System and a Hierarchy of Complexity Classes.
    JCSS 36, 254-276 (1988).

  • Курс Пола Бима. Lecture 9: Interactive Proofs and Arthur-Merlin Games.
  • Feige, Goldwasser, Lovasz, Safra, Szegedy. Interactive proofs and the hardness of approximating cliques. JACM, 1996.
  • Курс Джона Каца, лекция Даниэля Апона. Lecture 26 (про MIP=NEXP).

Дополнительная литература