R8. NP-Complete Problems
ฝัง
- เผยแพร่เมื่อ 5 ก.พ. 2025
- MIT 6.046J Design and Analysis of Algorithms, Spring 2015
View the complete course: ocw.mit.edu/6-0...
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
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?
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
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.
Its awesome to see TH-cam is recommending mother's lecture when son is delivering lecture... :D
Same thing happened with me XD
04:30 HamiltonianCycle ==> HamiltonianPath
13:00 K-CLIQUE ==> K-INDSET
21:50 K-CLIQUE ==> MAX2SAT
Great explanation! The first lecture that really makes sense... Very well explained in details. Very smart guy! Thank you, Amartya! Keep on!
What a brilliant young lecturer!
**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!
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.
Great recitation! The later the video the more tricky, creative and fun 🤣🤣
Great video!
Very comprehensible!
12:51, His style, juz bring it on.
I thought my player was stuck at double playback speed... thanks for the lecture Amartya!
Same here :)
Thank you, now everything is clear.
well explained! Thank you!
Great explanation! Thank you!
Great Explanation!
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
so you have you x by x latin square, lets say half the number in x are =1 and the other half of the numbers are =2, now we have a second latin grid with 1's and 2's, if we can solve that grid fast then we can rule out around half the possible numbers on the main latin square. Don't believe me try it for yourself. the real question is how long does it take to solve the 1's and 2's latin squares not whether the transformation works it works and should be easy to prove it works.
Given the completeness theorem what problem in proof theory about syntax does the SAT problem translate to?
INAUDIBLE: @6:03 ==> You can just start anywhere and visit all the vertices and stop
INAUDIBLE: @5:39 And, that problem is NP-Hard, so you can't solve it in polynomial time
great explanation
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?
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
23:12
very helpful
hope more examples could come up....
why do we have to create a dummy variable z???
excellent
Is there another lesson on this topic
"..you can't solve it polynomial then...", true if P != NP 5:38
He is so cute!
What the hell of that "Nintendo games or something" xDD
See lecture 16, they showed how to reduce 3SAT to a nintendo problem
There is a minor error in the "Clique - Independent set" reduction example. An edge is missing in the transformed graph.
Thanks a lot bud :)
Make sense?
no
make sense!!!!
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.
he's cute ^^
he's INDIAN
@@SHASHANKRUSTAGII wow a cute indian xd
definitely cute
THATS WHAT I THOUGHT
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
Isn't he hot in that jacket?
It really does not make sense!
👏👏
TH-cam why am i seeing this
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.
lets just say this is connected to this guy..haha
A potato would do better than this cameraman! Show the board!!! The board!!!!
👽
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
So many "so" and "dash" instead of "prime". But everything else is fine
IITian product 😎😎
this is too difficult to comprehend.
he sounds like an INDIAN.?
Yeah, Captain Obvious
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's an INDIAN