15. NP-Completeness

preview_player
Показать описание
MIT 18.404J Theory of Computation, Fall 2020
Instructor: Michael Sipser

Quickly reviewed last lecture. Covered NP-completeness; SAT and 3SAT; and more. Discussed a strategy for proving NP-completeness with a reduction from 3SAT by constructing gadgets that simulate variables and clauses.

License: Creative Commons BY-NC-SA

  1. MIT OpenCourseWare
  2. NP-complete
  3. polynomial-time reducible
  4. conjunctive normal form
Рекомендации по теме
15. NP-Completeness 1:25:53

15. NP-Completeness

16. Complexity: P, 1:25:25

16. Complexity: P, NP, NP-completeness, Reductions

R8. NP-Complete Problems 0:45:47

R8. NP-Complete Problems

NP-Completeness | Richard 0:16:26

NP-Completeness | Richard Karp and Lex Fridman

NP complete 0:34:32

NP complete

How do you 0:13:52

How do you 'solve' an NP Complete Problem?

P vs. NP 0:15:33

P vs. NP - The Biggest Unsolved Problem in Computer Science

P vs. NP: 0:19:44

P vs. NP: The Biggest Puzzle in Computer Science

CA Foundation | 4:52:04

CA Foundation | Maths | Permutation & Combination | In 100% English | For South Students

Computer Science: How 0:02:10

Computer Science: How to prove the NP-completeness of 15-Partition Problem? (2 Solutions!!)

NP-complete problems: Samuel's 0:27:27

NP-complete problems: Samuel's tutorial

N problem NP 0:02:09

N problem NP problem || NP hard and NP complete problem || design and analysis of algorithms | daa

Undergrad Complexity at 1:21:29

Undergrad Complexity at CMU - Lecture 15: coNP

P vs. NP 0:10:44

P vs. NP and the Computational Complexity Zoo

NP Completeness 1 0:09:26

NP Completeness 1 - Introduction to Hard Problems

NP hard and 0:18:27

NP hard and NP complete problems

Undergrad Complexity at 1:20:32

Undergrad Complexity at CMU - Lecture 12: NP-Completeness Reductions

NP-Complete Reductions: Clique, 0:13:23

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

NP Completeness 3 0:09:35

NP Completeness 3 - Definitions of Complexity Classes

NP Completeness 2 0:02:09

NP Completeness 2 - Listing some hard problems

F2021 CS 411/811 1:02:51

F2021 CS 411/811 Lecture 38 (NP-completeness, SAT, 3SAT, Vertex Cover, More NP-complete problems)

A&DS S02E15. Complexity 1:32:25

A&DS S02E15. Complexity Classes

NP Completeness of 0:06:18

NP Completeness of System of Linear Inequalities

What is NP-completeness? 0:01:29

What is NP-completeness? Explain NP-completeness, Define NP-completeness, Meaning of NP-completeness

Комментарии
Автор

Probably my favourite lecture up until now!!

MayankGoel
Автор

Just for clarity, for the 3SAT to CLIQUE conversion, the vertices of the graph are not the unique literals themselves, but rather for each clause in the formula there must be one vertex for each one of its literals. So formally, the vertices can be seen as ordered pairs (n, X), where n indicates a clause of the formula and X indicates one of its literals. Then the construction is that vertices (n, X) and (m, Y) are connected by an edge if and only if n≠m and the truth of X is consistent with the truth of Y.

connorfrankston
Автор

yay, i like that you mention the similarity between the symbols of reunion/disjunction and intersetion/conjunction

florianvanbondoc
Автор

Something that helps me remember the difference between the And and the Or symbols is the And looks kinda like an A

vyliad
Автор

What's the difference between verify and test? Seems to me they are not quite different...

QT-ytdb