It's a great video! If a viewer wants to look a little bit deeper, they could check section 7.2.2 of this PDF. ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2012/a9e76885a78c729f2375e14830caebf2_MIT6_046JS12_lec07.pdf
That title is amazing and you are doing a fine job, keep up the good work and I truly recommend a new mic when ever you can afford one at least a better headset mic
All trans women are men/males. Also, I noticed you’re subbed to a known convicted human trafficker and woman abuser “justin eric king” from destin Florida aka beau of the fifth column. You should unsubscribe, but don’t mind when White women from Eastern Europe get physically abused and have their labor abused in justin eric kings human trafficker scheme.
Thanks, broseph! Let me know if there are any other topics you're struggling with that you'd like to see covered, maybe I'll come out of semi RU-vid-retirement and slap another one of these bad boys together! Also maybe I won't, but you've gotta be in it to win it for sure.
Here are the values of x1,x2,...xn in the inequalities restricted to 0 or 1? If not I do not see how a solution for the linear inequalities can necessarily be translated to a solution of 3SAT. Could you clarify on this point?
Would solving for 'x's this way ever lead to a variable being positive value? since there's a zero weight edge connecting all of them so it looks like the delta() can never get larger than '0' and hence the solution will always be of variables zero or less than zero. Am i correct?
Yes you are, since BF finds the shortest path (minimum path) and there is cost 0 from Vo to any vertex, the only value that could replace it is one lower than 0.
I have come across this since I want to show inclusion in NP of a problem that can be reduced to this. Unfortunately, your argument for inclusion in NP is not sufficient, though. You say that, given values for x, one can obviously check in polynomial time whether A x <= b holds. This is clearly possible in time polynomial in |A|, |b| and |x|. But with this argument, any recursively enumerable problem would be in NP! For true inclusion in NP you need something stronger: this has to be possible in time polynomial in the size of the input to the original problem, i.e. polynomial in |A| and |b| only! Equivalently, you would have to show that one can always find a witnessing solution x of size polynomial in |A|+|b|. Is there any striking argument for that?
Its not clear, you have just described the procedure but not the logic behind it. To be specific you have not explained, why we are moving j to failure[j-1] when there is no match.
Hey William, That's the simplest and greatest way I have seen to understand this KMP algorithm and believe me you have done it really nice. Thank you and I hope we will continue to have such nice videos from your channel
I get how to do it. But I am just not satisfied cause I have not built an eye to see problems in the fashion yet. Pity me. One day though. Thanks, William.
