Курс «Сложность вычислений» (Компьютерные науки)

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