В чём заключается теорема Кука — Левина?

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

Другими словами, любая задача из класса NP может быть сведена к SAT за полиномиальное время с помощью детерминированной машины Тьюринга. en.wikipedia.org www.baeldung.com

Доказательство этой теоремы получил Стивен Кук в 1971 году, независимо в то же время её доказал советский математик Леонид Левин. ru.wikipedia.org habr.com

Пользователь

Время добавления