Сложность вычислений

  1. Вычислительные модели
  2. Оценки сложности
  3. Полиномиально разрешимые задачи
  4. Полиномиальные алгоритмы
  5. Теорема о иерархии и ее использование для доказательств трудно разрешимости
  6. Сведение задач друг к другу
  7. Сводимость и класс NP
  8. Доказательства NP полноты
  9. NP полные задачи
  10. Приближенное решение оптимизационных задач
  11. За пределами класса NP
  12. Задачи на полиномиальную иерархии и класс PSPACE
  13. Вероятностные полиномиальные алгоритмы
  14. PSPACE полнота
  15. Схемная сложность
  16. Приближенное решение оптимизационных задач
  17. Формульная сложность
  18. Интерактивные доказательства
  19. Интерактивные протоколы
  20. Односторонние функции и их использование
  21. Применения односторонних функций