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.

[shivendraiitkgp]

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.

[mayankchaturvedi]

a rare video that actually explains everything used. Deserves more upvotes

[thankgoditsover]

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.

[jeangeorge]

Your explanation > literally anything else > my teacher's explanation. Respects from Brazil (2).

[autumnevans]

I appreciate the non-jargon explanation using a concrete example. Thank you. I understand the reduction now.

[dhruvamin]

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.

[paulrykiel]

this was the best example I have ever seen, completely makes sense.Thank you

[harrywang]

that was actually really good explanation! My prof could never

[이지원학생경제학-ib]

This is the video I was looking for!! Thank you so much. You are way better than my professor

[AI-zwrz]

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

[wilmanlopez]

The best example I've found. Been looking for days!

[andreasleeb]

This video really deserves more views, helped me a lot to understand!

[sararezaeimanesh]

Amazing explanation. It answered all my questions. I was so confused. God bless you

[salookie]

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.

[mamtajakter]

Thanks Informal-CS for simply explaining the proof of subset sum is NPcom

[purushotams]

Your channel should have more subs and more views in videos. I really liked your content. Thanks! Keep creating.

[ven]

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.

[Mayheus]

could someone explain me why the 1 and 2s in the down right square?

[abelcoiffard]

Sir you just saved my semester. Many thanks

[bbbo]

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_*