A recent numberphile video brought me to this ( th-cam.com/video/5ovdoxnfFVc/w-d-xo.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
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!!!!!!!!!!!
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 :)
in the reduction, don't you also have to connect variables with their negation in the input for the graph so you are sure they don't get the same values, which is impossible input for circuit to be true and it's negation to also be true
No, the only "inputs" are the variables. The graph is structured to simulate a digital circuit whose inputs are labelled with distinct names of 0-1 valued variables. Negations of variables show up in the circuit/graph as outputs of NOT gates; they may not appear at all if the circuit doesn't use NOT gates.
@@albertrmeyer2336 I was working on reducing from vertex cover to graph coloring, but I couldn't find any sources, I was wondering if you have a way I go through :( all I'm thinking of is getting a complement of vertex cover graph, which would be a clique of size k and that will be the minimum colors
@@rouwo6115 I haven't thought about vertex cover in a (very) long time, so can't offer help now. I do wonder why you want to focus on this particular reduction.
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.
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
Thank you Septana. It is specially nice to be appreciated during this time of isolation.
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.
A recent numberphile video brought me to this ( th-cam.com/video/5ovdoxnfFVc/w-d-xo.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 :)
Your way of explaining things is amazing.
This is exactly what I was looking for, I wish I could thumbs up more than once
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!!!!!!!!!!!
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 :)
I'm currently taking a course about computational complexity and this video is great :), made everything clearer, very thankfull!
Shout out to this legend only good explanation on 3 coloring
That was a really clear explanation, thanks a lot :) I also love your energy
This class was awesome. Seriously, thank you so much!
Thanks a lot! Your way of explaining makes things really clear.
thanks professor, watching from pakistan
Best explanation. Thank u Prof
Thank you Prof! Still struggling to understand but I’ll definitely reference this video a lot :)
Logged in just to say thank you. Awesome explanation :)
amazing explanation, simple and clear
Really well explained, thank you for the video!
appreciate your help, love your teaching
Magnificent explanation !
Thanks alot! From one Albert to another :)
Thank you, great video!
Thank you. Well explained
Wonderful explanations! Thank you :)
2:39 my man predicted NFTs before they got big
Trank you so much for your explanation, it helped me a lot!
This is beautiful !
in the reduction, don't you also have to connect variables with their negation in the input for the graph so you are sure they don't get the same values, which is impossible input for circuit to be true and it's negation to also be true
No, the only "inputs" are the variables. The graph is structured to simulate a digital circuit whose inputs are labelled with distinct names of 0-1 valued variables. Negations of variables show up in the circuit/graph as outputs of NOT gates; they may not appear at all if the circuit doesn't use NOT gates.
@@albertrmeyer2336 oh I had this confused with the cnf formula, thank you!
@@albertrmeyer2336 I was working on reducing from vertex cover to graph coloring, but I couldn't find any sources, I was wondering if you have a way I go through :( all I'm thinking of is getting a complement of vertex cover graph, which would be a clique of size k and that will be the minimum colors
@@rouwo6115 I haven't thought about vertex cover in a (very) long time, so can't offer help now. I do wonder why you want to focus on this particular reduction.
@ no i wont win a million dollar :) just a problem i picked for an assignment and now i have nothing but regrets.
This is great thank you professor! ❤️
Amazing, Thank you
This helped, thanks!
great video
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/
Thank you for the explanation ,you are so handsome!
What a legend
Thanks
Legend
amazing
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