Объяснение NP-полной задачи (теорема Кука-Левина)

Что делает одну задачу «сложнее» другой? Как можно сказать, что задача является самой сложной в классе сложности? В этом видео мы представляем набросок доказательства теоремы Кука–Левина, вводя важнейшее понятие, известное как NP-полнота.

Автор: Кори Чанг
Продюсер: Вивиан Лю
Редактор сценария: Джастин Чен, Закари Гринберг, Элейн Чанг, Брэндон Чен
Музыка: Gravity Sound (   / @gravitysound  )

Твиттер:   / ubehavior  

—

Ссылки:
Плейлист «P против NP»:    • P vs NP  
Теорема Кука — Левина: https://en.wikipedia.org/wiki/Cook–Le...
NP-полнота: https://en.wikipedia.org/wiki/NP-полнота
Сокращение: https://ru.wikipedia.org/wiki/Снижени...)
SAT: https://ru.wikipedia.org/wiki/Проблем...
Circuit-SAT: https://ru.wikipedia.org/wiki/Проблем...
Схемы: https://ru.wikipedia.org/wiki/Проблем...
Машина Тьюринга: https://ru.wikipedia.org/wiki/Машина_...

Лекции:
NP-полнота и теорема Кука-Левина:    • Undergrad Complexity at CMU - Lecture 11: ...