Thanks to the following supporters of the channel for helping support this video. If you want to contribute, links are in the video description. Names are listed in alphabetical order by surname. Platinum: Micah Wood Silver: Simone Glinz, Josh Hibschman, Timmy Gy, Patrik Keinonen, Travis Schnider, and Tao Su
Dude! English is not even my first language and still ONLY YOU made sense of what is happening here to me. Thank you so much! I think you should consider adding "reduction from SAT" to the title since that is mainly what you explain here, so brightly. Bless you
Thanks for taking the time to make these videos :) Any chance you could cover TSP approximation algorithms? k-opt in particular would be interesting Thanks
If each clause is represented by a single node wouldn't that clause node be visited more than once if two or more of the elements in a clause are satisfied? I think you need a clause gadget.
Good video bro, thanks for explaining the proof. But you should prove the Hamiltonian path is NP-Complete transforming from the VERTEX-COVER to Hamiltonian path. It's an interesting way to prove the same that you did.
The edging of Hamiltonian path which has extreme resemblance with the ckt,we may observe in the case of Logistics management an algorithm goes to a differentiated phenomena to the reduction for a given set of edges.....the time and the drilled down variability waxing waning with time complexity shows a NP completeness at high.
Isn't a clause node visited multiple times by each variable gadget in that clause? Doesn't that mean that it is an invalid Hamilton path as a node is visited more than once? For example, if we had c_1 = ((X1) OR (NOT X2) OR (X3)), the variable gadgets corresponding to X1, X2 and X3 will all visit the node corresponding to c_1
Thanks to the following supporters of the channel for helping support this video. If you want to contribute, links are in the video description. Names are listed in alphabetical order by surname.
Platinum: Micah Wood
Silver: Simone Glinz, Josh Hibschman, Timmy Gy, Patrik Keinonen, Travis Schnider, and Tao Su
Dude! English is not even my first language and still ONLY YOU made sense of what is happening here to me. Thank you so much!
I think you should consider adding "reduction from SAT" to the title since that is mainly what you explain here, so brightly. Bless you
This guy brings the best energy. Hardest NP-complete reduction on the planet? Well, it's actually Very Easy. 😂
Thanks for taking the time to make these videos :)
Any chance you could cover TSP approximation algorithms? k-opt in particular would be interesting
Thanks
Crystal clear explanation.
thank you so much for your work!! I spend hours watching your videos when working on my homework :)
Absolutely Incredible!
thank you very much!!:))))))))))))
If each clause is represented by a single node wouldn't that clause node be visited more than once if two or more of the elements in a clause are satisfied? I think you need a clause gadget.
If multiple variables make the clause true, we can arbitrarily just pick one of them and ignore the others.
Good video bro, thanks for explaining the proof.
But you should prove the Hamiltonian path is NP-Complete transforming from the VERTEX-COVER to Hamiltonian path. It's an interesting way to prove the same that you did.
The edging of Hamiltonian path which has extreme resemblance with the ckt,we may observe in the case of Logistics management an algorithm goes to a differentiated phenomena to the reduction for a given set of edges.....the time and the drilled down variability waxing waning with time complexity shows a NP completeness at high.
Isn't a clause node visited multiple times by each variable gadget in that clause? Doesn't that mean that it is an invalid Hamilton path as a node is visited more than once? For example, if we had c_1 = ((X1) OR (NOT X2) OR (X3)), the variable gadgets corresponding to X1, X2 and X3 will all visit the node corresponding to c_1
My goodness is this channel wonderful!
Thank you so much
Great explanation
nice
Thank you!! This explanation is so clear.
Thanks
I didn't know charlie puth taught comp sci