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.
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.
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.
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_*
@@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
So where did the bottom rows of 4 come from? If you added another clause to this example would that number change? Thank you for this video by the way it is extremely specific and well explained!!
Thanks for the nice comment :) The 4 in the bottom rows come from the fact that each clause has at maximum 3 literals and thus each clause can be satisfied if it is satisfied by at least 1 literal and then with the help of the slack variable si and si' we can make it reach 4. But if a clause it not satisfied by any of the literals, then using both the slacks we won't be able to make 4. So, if we add another clause, the number 4 is not going to change. You will simply add one more column and 2 slack rows to go with it.
@@informal-cs3251 I got confused once again, when you said "each clause has at maximum 3 literals and thus each clause can be satisfied if it is satisfied by at least 1 literal (****understood till here****) and then with the help of the slack variable si and si' we can make it reach 4". Could you please explain in lil more simpler words that why to use the slack variables or the garbage values in order to reach "4". Sorry for being dumb now. Thanks in advance.
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?
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?
If you don't want to revise P, NP, Np-Complete and straightaway jump to the reduction then you should start viewing the video from 10:00.
a rare video that actually explains everything used. Deserves more upvotes
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.
Your explanation > literally anything else > my teacher's explanation. Respects from Brazil (2).
I appreciate the non-jargon explanation using a concrete example. Thank you. I understand the reduction now.
this was the best example I have ever seen, completely makes sense.Thank you
that was actually really good explanation! My prof could never
The best example I've found. Been looking for days!
Amazing explanation. It answered all my questions. I was so confused. God bless you
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.
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.
Thanks Informal-CS for simply explaining the proof of subset sum is NPcom
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 video really deserves more views, helped me a lot to understand!
Your channel should have more subs and more views in videos. I really liked your content. Thanks! Keep creating.
could someone explain me why the 1 and 2s in the down right square?
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.
Thank you, it clarifies many things to me
Awesome dude, finally i really understand. Respects from brazil
Thanks, the explanation helps a lot!
Thanks for clear explanation! it helps a lot and i'm just preparing my algorithm exam :)
Thanks, Sir. You helped me in this tutoriel!
Thanks bro, This helped a lot in understanding this concept.
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.
Fantastic video, thank you!
So where did the bottom rows of 4 come from? If you added another clause to this example would that number change? Thank you for this video by the way it is extremely specific and well explained!!
Thanks for the nice comment :)
The 4 in the bottom rows come from the fact that each clause has at maximum 3 literals and thus each clause can be satisfied if it is satisfied by at least 1 literal and then with the help of the slack variable si and si' we can make it reach 4. But if a clause it not satisfied by any of the literals, then using both the slacks we won't be able to make 4.
So, if we add another clause, the number 4 is not going to change. You will simply add one more column and 2 slack rows to go with it.
@@informal-cs3251 But if you replace all the "2" by "1" you can replace all the "4" by "3"?
@@Ahmed-wj5sd Yes, exactly. And you can imagine that you can put whatever you want and adjust the sum accordingly.
@@informal-cs3251 I got confused once again, when you said "each clause has at maximum 3 literals and thus each clause can be satisfied if it is satisfied by at least 1 literal (****understood till here****) and then with the help of the slack variable si and si' we can make it reach 4". Could you please explain in lil more simpler words that why to use the slack variables or the garbage values in order to reach "4". Sorry for being dumb now. Thanks in advance.
@@BiswaRanjanNanda I would like to understand this too. I don't understand either.
저를 살려주셔서 커다란 감사를 드립니다. 당신은 제 은인!
i struggled a lot on subset sum, thank u very much
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?
So helpful!!! Thank you so much!!!
Great video and very detailed. Thank you
Awesome explanation 👏
How to get the result of sum of subsets problem from this result?
Amazing Explanation! Thanks a lot
Sorry what happens after minuts 17:50....why 1/2 1/2 why t = 1/1/1/1 4/4/4/4 ?
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
But did u write 1's and 2's in last quadrant?
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?
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.
Great video, really helpful!
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.
Great video. Thanks!!!
12:43 Instead of brackets you can mention it as clauses
Great video man.
Nice one!
Thanks sir
well done bro #zeff eriction
Thank you
11/10 in confuesing
This works pretty well as ASMR hahaha!!
please prepare before shooting the video its a bit confusing.No offence
Thanks a lot! You explained it very well.
Great video, thanks!