Теорема Кука — Левина

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

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

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

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

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

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

Ссылки

• Sanjeev Arora, Boaz Barak. Complexity Theory: A Modern Approach