- 1
- 40 802
Informal-CS
Приєднався 19 лис 2018
Reduction : 3-CNF SAT to Subset Sum
This video discusses the 3-CNF SAT to Subset Sum reduction in order to show that Subset Sum is in NP-Complete.
Disclaimer: I am a 2nd year MS student and this is a very informal video intended to help those who want to understand the reduction.
Disclaimer: I am a 2nd year MS student and this is a very informal video intended to help those who want to understand the reduction.
Переглядів: 40 804
Sir you just saved my semester. Many thanks
Please make a complete series on this . thanks
11/10 in confuesing
Thanks bro, This helped a lot in understanding this concept.
well done bro #zeff eriction
저를 살려주셔서 커다란 감사를 드립니다. 당신은 제 은인!
Great video, thanks!
in the verification part you are telling that no matter how many helper variable we are going to take we can never reach 4. That's true but I am not getting that you yourself put the value of helper variable as 1 and 2 and claiming so. I want to say that if I wish I can take any random value in the helper variable and make the assignment true. So, basically you didn't tell any algorithm to fill the clause's helper value. is there any way to fill the helper value?
Your channel should have more subs and more views in videos. I really liked your content. Thanks! Keep creating.
But did u write 1's and 2's in last quadrant?
This video really deserves more views, helped me a lot to understand!
This video is a gem. One of the most beautiful explanations on the topics. Please, add NP, NP-Hard, and NP-Complete, etc to the keywords list or to the title. So that more people can access such an elegant lecture. The basic discussion on NP at the beginning was really amazing.
Hi, I would like to contact you. I like this video and your teaching style and I am an undergraduate student of CS who is interested in theoretical computer science such as this complexity theory. Is there anyway I would be able to do so?
please prepare before shooting the video its a bit confusing.No offence
Awesome explanation 👏 How to get the result of sum of subsets problem from this result?
Thank you so so much!!!
bhai badiya vedio hain, Indian Universities bhi chutiya kaata ab main MS kar raha hoon, US ki bhi universities bhi chutiya kaat rahi hain.
could someone explain me why the 1 and 2s in the down right square?
Amazing Explanation! Thanks a lot
The best example I've found. Been looking for days!
Thanks, the explanation helps a lot!
Amazing explanation. It answered all my questions. I was so confused. God bless you
Thanks, Sir. You helped me in this tutoriel!
a rare video that actually explains everything used. Deserves more upvotes
Note: The 1,2 on C1 through C4 can be 1, 1 and they all can add up to 3 instead of 4. It is one and the same thing.
I agree
12:43 Instead of brackets you can mention it as clauses
Thank you
Thank you, it clarifies many things to me
U can also make in similar graphic way for TSP and prove cook-levin therom of why 3sat is first npc ? It would be great.
that was actually really good explanation! My prof could never
Thanks for clear explanation! it helps a lot and i'm just preparing my algorithm exam :)
Fantastic video, thank you!
It might seems difficult when watching for the first time, but if you watch it for 2nd time then one would definitely understand it. But explanation is awsome.
Sorry what happens after minuts 17:50....why 1/2 1/2 why t = 1/1/1/1 4/4/4/4 ?
So helpful!!! Thank you so much!!!
Thanks for your explanation! One question: Do we determine the target value (1 1 1 4 4 4 4) and the value of the helper variables (1 and 2, on the right-down part) arbitrarily?
The number of 1s is dependent on the number of variables and the number of 4s is dependant on the number of clauses. This makes sense because the 1s are used to eliminate assignments where variables can be both true and false. And the 4s are used to eliminate assignments where none of the clauses are true.
For those that are confused by 4th quadrant here is what I understood SAT is satisfied if for all clauses, any one literal within each clause is satisfied However, it may be the case that more than one literal is satisfied within each clause but *Subset Sum* requires a specific target This is where the helpers come in These helpers help to hit the target if at least one literal is satisfied Lets think about a column with target = 4 and helpers {1, 2} If you add all the numbers in the helper, it becomes 3 which makes it impossible to hit the target unless you have at least one literal = True If you have 2 literals = True, then you only need to add 2 from the helper and you've reached the target *_The point is that as long as you have at least one literal within clause to satisfy the clause, you have made it possible to reach the target by using different sum of helpers_*
How to fix the target? like in this case 4?
@@chaitanyareddy5279 The 1s prevent variables from having 2 values, and the 4s are the number of clauses.
@@chaitanyareddy5279 You can select any target and then your helper values need to sum up to (target - 1), because you want the target to be satisfied only if at least one clause is satisfied.
@@stevenfletcher3389 are the 4's really the number of clauses ? My prof also used 4 as target but had the number of clauses variable (m). I am struggling a bit, because there may be an assignment, which satisfies all clauses in the sat problem, but needs 5 literals to be true. Then the target would be overshot ? Edit: I just understood it a bit better: because we are in 3cnf there are only three literals per clause 🙈🙈🙈 Therefore max 3 literals in one column can be 1 and with one helper line it sums up to 4
@@janniklasbertram9436 Yes, you're right. Your comment actually helped explain this to me.
Nice one!
I appreciate the non-jargon explanation using a concrete example. Thank you. I understand the reduction now.
Thanks a lot! You explained it very well.
Thanks sir
Your explanation > literally anything else > my teacher's explanation. Respects from Brazil (2).
The color coding helps to facilitate learning. I actually do that too in my documentation; use different colors to highlight and distinguish one part from another. Thanks for the tutorial as well. Makes sense how the helpers are used to get the sum or not get the sum.
Awesome dude, finally i really understand. Respects from brazil
i struggled a lot on subset sum, thank u very much
This works pretty well as ASMR hahaha!!
Great video, really helpful! <3 Can I request one on 3-SAT to Vertex Cover?
Nice explanation brother first i thought how i will mug up these things because tommorrow is my exam and now thanks to you i don't have to mug up
this was the best example I have ever seen, completely makes sense.Thank you
Thanks Informal-CS for simply explaining the proof of subset sum is NPcom