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

Доказательство этой теоремы, полученное Стивеном Куком в его фундаментальной работе в 1971 году, стало одним из первых важнейших результатов теории NP-полных задач. Независимо в то же время эта теорема была доказана советским математиком Леонидом Левиным .

В доказательстве теоремы Кука каждая задача из класса NP в явном виде сводится к SAT. С. Кук (S. Cook) определил класс NP задач следующим образом. Задача принадлежит классу NP, если:

1. решением задачи является один из двух ответов: «да» или «нет» ( );
2. требуемый ответ может быть получен на недетерминированном вычислительном устройстве за полиномиальное время.

Этот класс, как позже показал Р. Карп (R. Karp), в свою очередь содержит в себе другой широкий класс задач, названный Карпом NP-полные задачи , или NPC, сводимые в пределах этого класса одна к другой.

После появления результатов Кука была доказана NP-полнота для множества других задач. При этом чаще всего для доказательства NP-полноты некоторой задачи приводится полиномиальное сведение задачи SAT к данной задаче, возможно в несколько шагов, то есть с использованием нескольких промежуточных задач.

Примечания

Ссылки