Informal-CS
Informal-CS
  • 1
  • 40 802
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.
Переглядів: 40 804

Відео

КОМЕНТАРІ

  • @abelcoiffard5267
    @abelcoiffard5267 22 дні тому

    Sir you just saved my semester. Many thanks

  • @ShivamTiwari-yl7xv
    @ShivamTiwari-yl7xv Місяць тому

    Please make a complete series on this . thanks

  • @heybuddy_JAI_SHREE_RAM
    @heybuddy_JAI_SHREE_RAM 7 місяців тому

    11/10 in confuesing

  • @saketh1602
    @saketh1602 7 місяців тому

    Thanks bro, This helped a lot in understanding this concept.

  • @SonuKumar-q5o1b
    @SonuKumar-q5o1b Рік тому

    well done bro #zeff eriction

  • @ohtube99
    @ohtube99 Рік тому

    저를 살려주셔서 커다란 감사를 드립니다. 당신은 제 은인!

  • @Shai5757
    @Shai5757 Рік тому

    Great video, thanks!

  • @manmeetmuskan2599
    @manmeetmuskan2599 Рік тому

    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?

  • @purushotams175
    @purushotams175 Рік тому

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

  • @001afifafatima5
    @001afifafatima5 2 роки тому

    But did u write 1's and 2's in last quadrant?

  • @andreasleeb4085
    @andreasleeb4085 2 роки тому

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

  • @thankgoditsover
    @thankgoditsover 2 роки тому

    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.

  • @moatef1886
    @moatef1886 2 роки тому

    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?

  • @nihalrasuri1547
    @nihalrasuri1547 2 роки тому

    please prepare before shooting the video its a bit confusing.No offence

  • @sandeepmandrawadkar9133
    @sandeepmandrawadkar9133 2 роки тому

    Awesome explanation 👏 How to get the result of sum of subsets problem from this result?

  • @deepikaranipadmanaban1609
    @deepikaranipadmanaban1609 2 роки тому

    Thank you so so much!!!

  • @humbleguy9891
    @humbleguy9891 2 роки тому

    bhai badiya vedio hain, Indian Universities bhi chutiya kaata ab main MS kar raha hoon, US ki bhi universities bhi chutiya kaat rahi hain.

  • @Mayheus
    @Mayheus 2 роки тому

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

  • @aravindcheruvu2671
    @aravindcheruvu2671 3 роки тому

    Amazing Explanation! Thanks a lot

  • @wilmanlopez1742
    @wilmanlopez1742 3 роки тому

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

  • @chococ7651
    @chococ7651 3 роки тому

    Thanks, the explanation helps a lot!

  • @sararezaeimanesh3241
    @sararezaeimanesh3241 3 роки тому

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

  • @quatriceratus2695
    @quatriceratus2695 3 роки тому

    Thanks, Sir. You helped me in this tutoriel!

  • @mayankchaturvedi7671
    @mayankchaturvedi7671 3 роки тому

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

  • @ven7782
    @ven7782 3 роки тому

    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.

  • @manojmohan3406
    @manojmohan3406 3 роки тому

    12:43 Instead of brackets you can mention it as clauses

  • @ahmedwaleed519
    @ahmedwaleed519 3 роки тому

    Thank you

  • @reemattallah6148
    @reemattallah6148 3 роки тому

    Thank you, it clarifies many things to me

  • @mrkunalgoswami2010
    @mrkunalgoswami2010 4 роки тому

    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.

  • @harrywang6792
    @harrywang6792 4 роки тому

    that was actually really good explanation! My prof could never

  • @frankyang442
    @frankyang442 4 роки тому

    Thanks for clear explanation! it helps a lot and i'm just preparing my algorithm exam :)

  • @SZ-jw9my
    @SZ-jw9my 4 роки тому

    Fantastic video, thank you!

  • @dhruvamin197
    @dhruvamin197 4 роки тому

    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.

  • @claudiamesaaparicio8517
    @claudiamesaaparicio8517 4 роки тому

    Sorry what happens after minuts 17:50....why 1/2 1/2 why t = 1/1/1/1 4/4/4/4 ?

  • @xunjingwu260
    @xunjingwu260 4 роки тому

    So helpful!!! Thank you so much!!!

  • @BullishBuddy
    @BullishBuddy 4 роки тому

    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?

    • @kartheyansivalingam7927
      @kartheyansivalingam7927 3 роки тому

      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.

  • @bbbo85
    @bbbo85 5 років тому

    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
      @chaitanyareddy5279 4 роки тому

      How to fix the target? like in this case 4?

    • @stevenfletcher3389
      @stevenfletcher3389 3 роки тому

      @@chaitanyareddy5279 The 1s prevent variables from having 2 values, and the 4s are the number of clauses.

    • @arunas8685
      @arunas8685 3 роки тому

      @@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.

    • @janniklasbertram9436
      @janniklasbertram9436 Рік тому

      @@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

    • @stevenfletcher3389
      @stevenfletcher3389 Рік тому

      @@janniklasbertram9436 Yes, you're right. Your comment actually helped explain this to me.

  • @richardo-1997
    @richardo-1997 5 років тому

    Nice one!

  • @autumnevans2014
    @autumnevans2014 5 років тому

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

  • @Madnomad._
    @Madnomad._ 5 років тому

    Thanks a lot! You explained it very well.

  • @narendraparmar1631
    @narendraparmar1631 5 років тому

    Thanks sir

  • @jeangeorge6950
    @jeangeorge6950 5 років тому

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

  • @salookie8000
    @salookie8000 5 років тому

    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.

  • @icarovieira3680
    @icarovieira3680 5 років тому

    Awesome dude, finally i really understand. Respects from brazil

  • @dango2404
    @dango2404 5 років тому

    i struggled a lot on subset sum, thank u very much

  • @Elegyofawesomeness
    @Elegyofawesomeness 5 років тому

    This works pretty well as ASMR hahaha!!

  • @dooplevey
    @dooplevey 5 років тому

    Great video, really helpful! <3 Can I request one on 3-SAT to Vertex Cover?

  • @AI-zw1rz
    @AI-zw1rz 5 років тому

    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

  • @paulrykiel6900
    @paulrykiel6900 5 років тому

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

  • @mamtajakter6787
    @mamtajakter6787 6 років тому

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