Теорема Кука
Материал из Википедии — свободной энциклопедии
Теорема. Задача о выполнимости булевой формулы в КНФ (SAT) является NP-полной.
Доказательство этой теоремы, полученное Стивеном Куком в его фундаментальной работе в 1971 году, стало одним из первых важнейших результатов теории NP-полных задач.
В доказательстве теоремы Кука каждая задача из класса NP в явном виде сводится к SAT. После появления результатов Кука была доказана NP-полнота для множества других задач. При этом чаще всего для доказательства NP-полноты некоторой задачи приводится полиномиальное сведение задачи SAT к данной задаче, возможно в несколько шагов, то есть с использованием нескольких промежуточных задач.
[править] Ссылки
 |
Это незавершённая статья по математике. Вы можете помочь проекту, исправив и дополнив её. |
