Видеолекции курса «Сложность вычислений»

  1. Вычислительные модели. Машины Тьюринга и арифметические алгоритмы.
  2. Теорема об иерархии. Сведение задач друг к другу.
  3. Класс NP. Сведение задач друг к другу.
  4. Теорема Кука-Левина. Доказательства NP полноты.
  5. #P полные задачи. Сведения задач подсчета друг к другу.
  6. PSpace полные задачи. Определение вычислительной сложности проблем.
  7. Вероятностные алгоритмы. Схемная сложность.
  8. Интерактивные доказательства. Схемная сложность.
  9. Доказательства с нулевым разглашением (Zero knowledge proof). Односторонние функции.
  10. Односторонняя функция
  11. Применения односторонних функций. Односторонние функции.