Loading AI tools
З Вікіпедії, вільної енциклопедії
Теорема Кука — Левіна (також просто теорема Кука ) стверджує, що задача здійсненності бульових формул у КНФ (коротше, SAT) є NP — повною.
Доведення цієї теореми, отримане Стівеном Куком у його фундаментальній роботі в 1971 році, стало одним з перших найважливіших результатів теорії NP-повних задач. Незалежно в той же час ця теорема була доведена радянським математиком Леонідом Левіним
.
У доведенні теореми Кука кожна задача з класу NP у явному вигляді зводиться до SAT. С. Кук визначив клас NP задач розпізнавання властивостей наступним чином. Задача належить класу NP, якщо :
Цей клас, як пізніше показав Річард Карп, у свою чергу містить у собі інший широкий клас задач, названий Карпом NP-повні задачі, або NPC, — задачі, які зводяться в межах цього класу одна до одної.
Після появи результатів Кука була доведена NP-повнота для безлічі інших завдань. При цьому найчастіше для доказу NP-повноти деякої задачі наводиться поліноміальне зведення задачі SAT до даної задачі, можливо в кілька кроків, тобто з використанням декількох проміжних задач.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.