Программа Гильберта, NP ≠ P, Рефлексия
Оглавление
1. Задачи из классов NP и P, NP+ и P+ – 4 страницы
2. Программа Гильберта и теория алгоритмов – 3,5 страницы
3. Сложность вопроса о NP ≠ P – 1,5 страницы
4. Предварительное замечание о программе Гильберта для теории алгоритмов – 1,5 страницы
5. Диагонализация.
5.1. Лемма о диагонализации – 3 страницы
5.2. Теорема о построении алгоритма, применяемого к себе – 2,5 страницы
6. Задачи Кука и авторизуемые задачи из класса NP – 8 страниц
п. 1, пп. 2.1-2.3, пп. 2.4-3, пп. 4-5.
7. NP ≠ P – 8,5 страниц
пп. 1-3, пп. 4-5, пп. 6.1-6.3, пп. 6.4-7.
8. Приложения
8.1. Первая теорема Гёделя о неполноте – 3 страницы
8.2. Вторая теорема Гёделя о неполноте – 2,5 страницы