R8. NP-Complete Problems
ฝัง
- เผยแพร่เมื่อ 3 มี.ค. 2016
- MIT 6.046J Design and Analysis of Algorithms, Spring 2015
View the complete course: ocw.mit.edu/6-046JS15
Instructor: Amartya Shankha Biswas
In this recitation, problems related to NP-Completeness are discussed.
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu
![[TH] 2024 PMWC x EWC Main Tournament Day 1 | PUBG MOBILE WORLD CUP x ESPORTS WORLD CUP](http://i.ytimg.com/vi/f5Coja1zCzo/mqdefault.jpg)
4:34 Hamiltonian cycle -> Hamiltonian Path
13:00 Clique -> Independent Set
karan patel thanks
My dude walked in straight from the afterparty. Respect!
thought I was the only one that noticed
how did you know?
Great explanation! The first lecture that really makes sense... Very well explained in details. Very smart guy! Thank you, Amartya! Keep on!
I have a professor that I pearly understand what he was talking about for like four classes with total 12 hours. However, all that I can say is thank you so much. I am really glad to have knowledge from a person like you.
After showing several videos about NP Problems and reductions (especially in graph theory), it's the first time that I could find such an intuitive lecture and understand these problem. Thank you Amartya!!
He went fast, but still did well
04:30 HamiltonianCycle ==> HamiltonianPath
13:00 K-CLIQUE ==> K-INDSET
21:50 K-CLIQUE ==> MAX2SAT
Great video!
Very comprehensible!
**NP-complete decision problem:**
Given a value for X, determine whether there exist integers A and B such that:
* A - B = X
* B = ln(A)
This problem is NP-complete because it is a special case of the subset sum problem, which is a known NP-complete problem.
**Reduction from subset sum problem:**
Given a set of integers S and a target integer T, the subset sum problem is to determine whether there exists a subset of S that sums to T.
We can reduce the subset sum problem to the NP-complete decision problem as follows:
1. Let S = {a1, a2, ..., an} be the set of integers and T be the target integer.
2. Create a new integer X = T + 1.
3. Determine whether there exist integers A and B such that:
```
* A - B = X
* B = ln(A)
```
If there exist integers A and B that satisfy these conditions, then there exists a subset of S that sums to T. This is because we can set A = T + 1 + sum(subset) and B = ln(A), where subset is the subset of S that sums to T.
Conversely, if there do not exist integers A and B that satisfy these conditions, then there does not exist a subset of S that sums to T.
Therefore, the NP-complete decision problem is NP-complete.
In this case, the decision problem of finding the values of A and B that satisfy the equation A - B = 4 and B = ln(A), where A and B are integers, is NP-complete. However, there do not exist any integers that satisfy this equation.
Therefore, we can conclude that P does not equal NP.
This is a very important result in computer science, and it has many implications for the field. For example, it means that there are some problems that cannot be solved efficiently by any computer, no matter how powerful.
Nice video presented by a clever guy. I really like the video!
Its awesome to see TH-cam is recommending mother's lecture when son is delivering lecture... :D
Same thing happened with me XD
What a brilliant young lecturer!
Given the completeness theorem what problem in proof theory about syntax does the SAT problem translate to?
Thank you, now everything is clear.
Great recitation! The later the video the more tricky, creative and fun 🤣🤣
Great explanation! Thank you!
well explained! Thank you!
we have to show number of clauses to be more than k then what's the need of E' and k as only V number of clauses should be sufficient, isn't it?
5:40 how? Aren't we supposed to not repeat any vertex in Hamaltonion cycle?
kind of wanted to see him talk about turan's theorem
why do we have to create a dummy variable z???
Is there another lesson on this topic
Great Explanation!
Amazing video overall, really appreciate it.
One note of feedback from me:
I got confused for a while at 31:47 because I thought you were writing out subtractions.
Once I rewinded a bit to listen to how you defined V' , then the 3 clauses became clear to me.
hope more examples could come up....
great explanation
12:51, His style, juz bring it on.
Since 2sat is in P, can anyone explain the difference between max2sat and 2 sat?
2 sat is whether if there is an assignment to the literals so ALL clauses are satisfied; max2sat is whether there is an assignment to the literals so at least K clauses are satisfied. So s sat is a special case of max2sat, where k = number of clauses. If that helps.
There is a minor error in the "Clique - Independent set" reduction example. An edge is missing in the transformed graph.
What is the definition of Z? what's its role?
I think it's an arbitrary addition to the literals for the purpose of isolating certain vertices
It’s an additional variable to prevent a zero solution: Without z you can set x_i = 0 for all i and obtain the maximum, since all (not x_i or not x_j) would be 1.
Adding constraints with z prevents this. Note, however, that z is still a variable and thus is either 1 or 0, still potentially allowing a zero solution. Adding a constraint on both z and not z prevents the zero solution.
For example:
No z:
x_i = 0 for all i
-> (not x_i or not x_j) = 1 for all (i, j) in c(E)
-> All constraints are fullfilled, i.e. the maximal solution
Only constraint with z:
x_i = 0 for all i, z = 1
-> (not x_i or not x_j) = 1 for all (i, j) in c(E) and (x_i or z) = 1 for all i in V
-> All constraints are fullfilled, i.e. maximal solution
Constraints on both:
x_i = 0 for all i, z = 1
-> (not x_i or not x_j) = 1 for all (i, j) in c(E) and (x_i or z) = 1 [always fulfilled!] and (x_i or not z) = 0 for all i in V
-> Potentially not maximal! Changing one x_k to 1 already increases the number of fulfilled constraint by 1, namely: (x_k or not z) = 1
I thought my player was stuck at double playback speed... thanks for the lecture Amartya!
Same here :)
Make sense?
no
Thanks a lot bud :)
very helpful
excellent
23:12
INAUDIBLE: @5:39 And, that problem is NP-Hard, so you can't solve it in polynomial time
INAUDIBLE: @6:03 ==> You can just start anywhere and visit all the vertices and stop
make sense!!!!
What the hell of that "Nintendo games or something" xDD
See lecture 16, they showed how to reduce 3SAT to a nintendo problem
He is so cute!
It really does not make sense!
👏👏
"..you can't solve it polynomial then...", true if P != NP 5:38
TH-cam why am i seeing this
Take your coat off--stay awhile.
Maybe he is cold.
Man's not hot
Style is everything
this guy explains well...doesn't actually matter whether he wears a coat or not
he's cute ^^
he's INDIAN
@@SHASHANKRUSTAGII wow a cute indian xd
definitely cute
THATS WHAT I THOUGHT
So many "so" and "dash" instead of "prime". But everything else is fine
Isn't he hot in that jacket?
As far as I know 2SAT is in P and Max Clique is NP-Complete. Sorry to say but I did not understand this lecture at all.
Because you missed the word "max" in front of 2SAT. The example wasn't about 2SAT, which is indeed in P, it was about max2SAT. Max2SAT is NP complete and this is what was shown in this lecture.
@@victos-vertex damn you came with some attitude
👽
lets just say this is connected to this guy..haha
this is too difficult to comprehend.
Not helpful at all ! waste 20 minutes of my time + 2 min for this comment. He can use little example for some reduction e.g. max2sat reduction from k-clique, that was so unclear to me.
A potato would do better than this cameraman! Show the board!!! The board!!!!
I never understood why so many teachers insist on using a chalk board instead of a computer to explain things about programming
i wouldn't really say this lecture is about programming
he sounds like an INDIAN.?
Yeah, Captain Obvious
IITian product 😎😎
He's an INDIAN