W11L61_SUBSET-SUM is NP-Complete

Автор: NPTEL-NOC IITM

Загружено: 2023-05-11

Просмотров: 1444

Описание:

00:00 - Recap
01:00 - Subset-Sum
02:40 - Subset-Sum is NP-Complete
04:05 - Construct a reduction from 3-SAT to Subset Sum
19:15 - Correctness of the reduction
19:35 - Proving the forward direction of the correspondence
28:12 - Proving the other direction of the correspondence
37:20 - Summary

W11L61_SUBSET-SUM is NP-Complete

Доступные форматы для скачивания:

Скачать видео mp4

Информация по загрузке:

Скачать аудио mp3

Похожие видео

W11L62_Knapsack Problem

W11L62_Knapsack Problem

8. NP-Hard and NP-Complete Problems

8. NP-Hard and NP-Complete Problems

Гамильтонов путь является NP-полным (направленным, сокращение от 3SAT)

Гамильтонов путь является NP-полным (направленным, сокращение от 3SAT)

Algorithms Lecture 35: NP-Completeness (3) Reduction Examples, Segment 3: Subset Sum & Set Partition

Algorithms Lecture 35: NP-Completeness (3) Reduction Examples, Segment 3: Subset Sum & Set Partition

Theory of Computation_Prof. Subrahmanyam Kalyanasundaram

Theory of Computation_Prof. Subrahmanyam Kalyanasundaram

SubsetSum

Сумма и разбиение подмножеств являются NP-полными — Теория сложности — Разработка и анализ алгори...

Сумма и разбиение подмножеств являются NP-полными — Теория сложности — Разработка и анализ алгори...

Обыграешь меня — дам $1 000 000», — смеялся профи, не зная, что дочь горничной — гений

Обыграешь меня — дам $1 000 000», — смеялся профи, не зная, что дочь горничной — гений

Vertex Cover is NP-Complete + Example

Vertex Cover is NP-Complete + Example

Hamiltonian Cycle is NP-Complete (Algorithms 24)

Hamiltonian Cycle is NP-Complete (Algorithms 24)

Каково это — изобретать математику?

Каково это — изобретать математику?

P, NP and Approximation Algorithms: Prof. Naveen Garg, IIT-Delhi

P, NP and Approximation Algorithms: Prof. Naveen Garg, IIT-Delhi

Вейвлеты: математический микроскоп

Вейвлеты: математический микроскоп

Как сжимаются изображения? [46 МБ ↘↘ 4,07 МБ] JPEG в деталях

Как сжимаются изображения? [46 МБ ↘↘ 4,07 МБ] JPEG в деталях

W11L59_CLIQUE and VERTEX-COVER is NP-Complete

W11L59_CLIQUE and VERTEX-COVER is NP-Complete

Logarithms... How? (NancyPi)

Logarithms... How? (NancyPi)

The Mathematician's Weapon | An Intro to Category Theory, Abstraction and Algebra

The Mathematician's Weapon | An Intro to Category Theory, Abstraction and Algebra

Алгоритмы на Python 3. Лекция №1

Алгоритмы на Python 3. Лекция №1

NP-Complete Reductions: Clique, Independent Set, Vertex Cover, and Dominating Set

NP-Complete Reductions: Clique, Independent Set, Vertex Cover, and Dominating Set

DAA- NP complete (Vertex Cover Problem)

DAA- NP complete (Vertex Cover Problem)