Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Статистика
На русском, статей
Улучшено за 24 ч.
Добавлено за 24 ч.
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

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

Из Википедии — свободной энциклопедии

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

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

В доказательстве теоремы Кука каждая задача из класса NP в явном виде сводится к SAT. С. Кук (S. Cook) определил класс NP задач распознавания свойств следующим образом. Задача принадлежит классу NP, если:

  1. решением задачи является один из двух ответов: «да» или «нет» (задача распознавания свойств);
  2. требуемый ответ может быть получен на недетерминированном вычислительном устройстве за полиномиальное время.

Этот класс, как позже показал Р. Карп (R. Karp) в свою очередь содержит в себе другой широкий класс задач, названный Карпом NP-полные задачи, или NPC, сводимые в пределах этого класса одна к другой.

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

Энциклопедичный YouTube

  • 1/3
    Просмотров:
    1 312
    1 401
    648
  • 004. Теорема Кука-Левина. Доказательства NP полноты - Н.К.Верещагин
  • 002. Теорема об иерархии. Сведение задач друг к другу - Н.К.Верещагин
  • NP-полные задачи

Субтитры

Примечания

  1. Л. А. Левин. Универсальные задачи перебора (рус.) // Проблемы передачи информации. — 1973. — Т. 9, № 3. — С. 115—116.

Ссылки

Эта страница в последний раз была отредактирована 10 июля 2020 в 12:23.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).