Теорема Кука Левіна також просто теорема Кука стверджує що задача здійсненності бульових формул у КНФ коротше SAT є NP п

Теорема Кука — Левіна (також просто теорема Кука ) стверджує, що задача здійсненності бульових формул у КНФ (коротше, SAT) є NP — повною.

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

У доведенні теореми Кука кожна задача з класу NP у явному вигляді зводиться до SAT. С. Кук визначив клас NP задач наступним чином. Задача належить класу NP, якщо :

Розв'язком задачі є одна з двох відповідей: «так» чи «ні» () ;
Потрібна відповідь може бути отримана на недетермінірованому обчислювальному пристрої за поліноміальний час.

Цей клас, як пізніше показав Річард Карп, у свою чергу містить у собі інший широкий клас задач, названий Карпом NP-повні задачі, або NPC, — задачі, які зводяться в межах цього класу одна до одної.

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

Посилання

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