8. Формальное определение алгоритма через рекурсивные функции (примитивно рекурсивные и частично рекурсивные).

9. Полиномиальная сводимость языков и задач. Np полные задачи. Детерминированные и не детерминированные машины класса p и pn. Теорема Кука.

P задачи – класс задач, которые возможно решить на детерминированной машине Тьюринга за полиномиальное время.

NP задачи – класс задач, которые возможно решить на недетерминированной машине Тьюринга за полиномиальное время. Задача называется NP-полной, если она принадлежит классу NP и любая другая задача из NP сводится к ней за полиномиальное время.

Теорема Кука — Левина (также просто теорема Кука) утверждает, что за­да­ча о вы­пол­ни­мо­сти булевой формулы в КНФ яв­ля­ет­ся NP-пол­ной.