Сложность алгоритмов

1. Машины Тьюринга и арифметические алгоритмы.

2. Теорема об иерархии. Сведение задач друг к другу.

3. Класс NP. Сведение задач друг к другу.

4. Теорема Кука-Левина. Доказательства NP полноты.

5. Приближенное решение задач оптимизации.

6. #P полные задачи. Сведения задач подсчета друг к другу.

7. PSpace полные задачи. Определение вычислительной сложности проблем.

8. Вероятностные алгоритмы. Схемная сложность.

9. Интерактивные доказательства. Схемная сложность.

10. Доказательства с нулевым разглашением. Односторонние функции.

Источник: vk.com

Комментарии: