Really appreciated sir. Your video saves me from algorithm homework-hell, it's so clear and good for understanding. I'll try my best to get in MIT(or at least pay a visit) in the future :)
Watching this before my final tomorrow and this blessed my brain which has been seriously damaged by this np completeness thing, it might be just np complete but it has definitely been np hard on my brain, thank you for making this you are AMAZINGGGGGG!!!!!!!!!!!
A recent numberphile video brought me to this ( ua-cam.com/video/5ovdoxnfFVc/v-deo.html ) and seems to indicate (17:50 and onward) that 3SAT reduces not only to the 3-coloring of a graph, but to that of a planar graph or map (I have to admit I'm not even sure if they're equivalent). The graphs you show for the NOT and OR gates are clearly planar, but is this still valid if you simply merge two OR graphs as presented at 11:50? Otherwise, is there a different way to merge such gates to preserve their being planar?
No, if the circuit is not planar, then the graph you get by replacing gates with gadgets wont be planar either. The fix is to use a "crossover" graph gadget as explained at the end of the video; see for example www.google.com/search?q=3-color+crossover+gadget&client=firefox-b-1-d&sa=X&biw=1308&bih=738&sxsrf=ALeKk03hFpLt77J3Qw1pAtfNYBI209N4ag:1612981252476&tbm=isch&source=iu&ictx=1&fir=UOcOpPRNr48EgM%252CWHUwKr79OAnvqM%252C_&vet=1&usg=AI4_-kQ0xVtnXvfyfLuXDf0Sw6VxIJUZdA&ved=2ahUKEwig1dS099_uAhVphOAKHdbDBywQ9QF6BAgIEAE#imgrc=UOcOpPRNr48EgM
Michael Paterson devised a simpler (but still ingenious) 3-color crossover gadget than the one in Stockmeyer's thesis. A quick google search led me to the gadget in lecture 9 notes, page 4: ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/lecture-notes/
@@ianleo3030 I'd say that in the worst case, deciding SAT formulas with up to 60 variables and 1000 connectives in less than a million years will be completely out of reach forever. I would not want to predict about the possibility of someday being able to decide such formulas on average within a few minutes.
This is fantastic! Never have I ever heard and seen such a clear, cogent, and concise explanation of this concept. Thank you sir for sharing this.
Thank you Septana. It is specially nice to be appreciated during this time of isolation.
I've seen this problem for the first time 4 years ago, but this is the first time I see such a complete and simple explanation
It's amazing to see a person who really understands a hard topic.
This is the best video I've seen on the topic. Thank you.
Really appreciated sir. Your video saves me from algorithm homework-hell, it's so clear and good for understanding. I'll try my best to get in MIT(or at least pay a visit) in the future :)
Shout out to this legend only good explanation on 3 coloring
Your way of explaining things is amazing.
Thank you so much! I was studying NP-completeness and this video was a gem....
I'm currently taking a course about computational complexity and this video is great :), made everything clearer, very thankfull!
This is exactly what I was looking for, I wish I could thumbs up more than once
That was a really clear explanation, thanks a lot :) I also love your energy
Watching this before my final tomorrow and this blessed my brain which has been seriously damaged by this np completeness thing, it might be just np complete but it has definitely been np hard on my brain, thank you for making this you are AMAZINGGGGGG!!!!!!!!!!!
This class was awesome. Seriously, thank you so much!
Thank you Prof! Still struggling to understand but I’ll definitely reference this video a lot :)
Magnificent explanation !
Thanks a lot! Your way of explaining makes things really clear.
Best explanation. Thank u Prof
Logged in just to say thank you. Awesome explanation :)
thanks professor, watching from pakistan
Amazing, Thank you
amazing explanation, simple and clear
appreciate your help, love your teaching
Really well explained, thank you for the video!
Thanks alot! From one Albert to another :)
Thank you. Well explained
Wonderful explanations! Thank you :)
Thank you, great video!
This is beautiful !
great video
Trank you so much for your explanation, it helped me a lot!
This is great thank you professor! ❤️
Legend
This helped, thanks!
A recent numberphile video brought me to this ( ua-cam.com/video/5ovdoxnfFVc/v-deo.html ) and seems to indicate (17:50 and onward) that 3SAT reduces not only to the 3-coloring of a graph, but to that of a planar graph or map (I have to admit I'm not even sure if they're equivalent). The graphs you show for the NOT and OR gates are clearly planar, but is this still valid if you simply merge two OR graphs as presented at 11:50? Otherwise, is there a different way to merge such gates to preserve their being planar?
No, if the circuit is not planar, then the graph you get by replacing gates with gadgets wont be planar either. The fix is to use a "crossover" graph gadget as explained at the end of the video; see for example
www.google.com/search?q=3-color+crossover+gadget&client=firefox-b-1-d&sa=X&biw=1308&bih=738&sxsrf=ALeKk03hFpLt77J3Qw1pAtfNYBI209N4ag:1612981252476&tbm=isch&source=iu&ictx=1&fir=UOcOpPRNr48EgM%252CWHUwKr79OAnvqM%252C_&vet=1&usg=AI4_-kQ0xVtnXvfyfLuXDf0Sw6VxIJUZdA&ved=2ahUKEwig1dS099_uAhVphOAKHdbDBywQ9QF6BAgIEAE#imgrc=UOcOpPRNr48EgM
@@albertrmeyer2336 That's brilliant, thank you for the quick response and the amazing content :)
Thanks
What a legend
amazing
Thank you for the explanation ,you are so handsome!
Can anyone point me to Dr. Stockmeyer's planar graph result for the OR gadget?
Michael Paterson devised a simpler (but still ingenious) 3-color crossover gadget than the one in Stockmeyer's thesis. A quick google search led me to the gadget in lecture 9 notes, page 4:
ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-890-algorithmic-lower-bounds-fun-with-hardness-proofs-fall-2014/lecture-notes/
2:39 my man predicted NFTs before they got big
Please just Why can't be more than one assignment lead the circuit-SAT to be satisfiable
there can be more than one.
@@albertrmeyer2336 last thing how many different variables and classes when computers will no longer be able to slove a sat problem in polynomial time
@@albertrmeyer2336 thanks
@@ianleo3030 I'd say that in the worst case, deciding SAT formulas with up to 60 variables and 1000 connectives in less than a million years will be completely out of reach forever. I would not want to predict about the possibility of someday being able to decide such formulas on average within a few minutes.
google stuff