1
Шаг 1. Сложность задачи. Основные понятия
Шаг 2. Понятие переборной задачи (задачи решаемой с помощью полного перебора)
Шаг 3. Понятие задачи распознавания
Шаг 4. Понятие полиномиальной сводимости
Шаг 5. Класс сложности NP
Шаг 6. Теорема о принадлежности задачи ВЫПОЛНИМОСТЬ классу NP
Шаг 7. Связь между классами P и NP
Шаг 8. Классы сложности P, NP, NPI, NPC
Шаг 9. Задача о k-выполнимости
Шаг 10. Теорема о полиномиальной сводимости задачи ВЫПОЛНИМОСТЬ к задаче 3-ВЫПОЛНИМОСТЬ
Шаг 11. Классы сложности NPI, NPC
1