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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

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

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

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

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

Посилання

[ред. | ред. код]