Great video! Came to TH-cam as my cs professor did not explain this 3 SAT -> subset sum reduction clearly. Your explanation was thorough and clear! Please continue to create great content like this, it would be greatly appreciated by CS students like me. Cheers!
Very clear explanation - Thanks! One Question: What would we do, if we insist, that the numbers given as instance for the SUBST SUM problem are different to each other?
He's talking about the sum for any of the columns being >= 10. In that case you'd have to carry over the one to the next column and your reduction is shafted. H explains it at 15:59
The subset sum problem does not care about how the numbers are encoded. The subset sum problem only cares that the numbers are in fact integers. The encoding is completely irrelevant. It's the same problem regardless.
Great video! Came to TH-cam as my cs professor did not explain this 3 SAT -> subset sum reduction clearly. Your explanation was thorough and clear! Please continue to create great content like this, it would be greatly appreciated by CS students like me. Cheers!
This was a very helpful explanation. The part after 13:00 was especially helpful explaining the purpose of the additional rows
Very clear explanation - Thanks!
One Question:
What would we do, if we insist, that the numbers given as instance for the SUBST SUM problem are different to each other?
O.K., the solution is given at the end!
when you say to read the numbers as decimal numbers, what do you mean by that?
Not to read them in binary, of course. So 1001 is One Thousand and one and not 9, for example.
Also, what do you mean by there not being any carryovers?
I think when you add variables for w there should be no carryovers, means that we cannot take a literal and its negation in the same clause
He's talking about the sum for any of the columns being >= 10. In that case you'd have to carry over the one to the next column and your reduction is shafted. H explains it at 15:59
@@elliotfouts5939 Exactly!
The subset sum problem does not care about how the numbers are encoded.
The subset sum problem only cares that the numbers are in fact integers.
The encoding is completely irrelevant. It's the same problem regardless.
Hervorragend!
you should get to the point faster in your vids, thanks.
No, I like it this way. Gives me time to process.
you really don't explain things well
🥺