Теорема Кука

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

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

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

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

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

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

Примечания

1. ↑ Л. А. Левин Универсальные задачи перебора (рус.) // Проблемы передачи информации. — 1973. — Т. 9. — № 3. — С. 115—116.

Ссылки

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