Beautiful! This is the perfect and essential supplement that I never got in my CS classes. I can't wait to start cranking out SAT equations with ChatGPT to solve all kinds of puzzles! I always wondered if there's a way to combine polynomial systems of equations with coefficients provided by a SAT solver, in such a way as to construct piecewise functions. This would enable you to analyze resnets or any kind of piecewise system.
Professor Meyer, I have a question (if you're reading these comments). The method you use to convert graph G to proposition propG produces a proposition with many terms. If you were to take propG and use the 'gizmo method' to turn it into a graph, you'd get a new graph G1 that would be much larger than the original graph G. If one were to continue iterating in this manner, you could generate a 'family' of graphs G1, G2, G3...GN that are all 'related'. Is there any way to reverse this process? If we were to start with huge graph GN, is there any way would could extract the 'kernel graph' G?
I haven't heard of the "gizmo" method, but these kinds of transformations between graphs and formulas are typically reversible, and if so, reconstructing G1 from GN would be doable. I don't see the point in doing this though.
@@albertrmeyer2336 Sorry - the gizmo method is what I was referring to as the method you present in your other sat to 3color video, where you replace each logic gate of the circuit with a 'graph gadget' and hook the gadgets together to produce the graph whose colorability is equivalent to the satifiability of the circuit/proposition. I heard the gadgets referred to as gizmos elsewhere and that's the name the stuck in my mind. It seems to me that if you could reverse the process and get graph G1 from graph GN that this might be a process whereby we could 'compress' arbitrary graphs - if they are 'compressible' in this sense. The reason I'm interested in this is because I'm looking into graphs as possible compressed representations of shapes (for computer graphics). Thanks for your reply, and for the excellent videos BTW.
@@aaronkambeitz4875 The G1...GN sequence of graphs will be very special, and the ability to recover G1 from GN is unlikely to be relevant to "compressing" general graphs. I have seen some recent results on finding small subnets of large neural nets that serve about equally as well at pattern classification; I don't have references handy, but googling might lead you to the relevant research.
Beautiful! This is the perfect and essential supplement that I never got in my CS classes. I can't wait to start cranking out SAT equations with ChatGPT to solve all kinds of puzzles! I always wondered if there's a way to combine polynomial systems of equations with coefficients provided by a SAT solver, in such a way as to construct piecewise functions. This would enable you to analyze resnets or any kind of piecewise system.
You are truly awesome.
Professor Meyer, I have a question (if you're reading these comments). The method you use to convert graph G to proposition propG produces a proposition with many terms. If you were to take propG and use the 'gizmo method' to turn it into a graph, you'd get a new graph G1 that would be much larger than the original graph G. If one were to continue iterating in this manner, you could generate a 'family' of graphs G1, G2, G3...GN that are all 'related'. Is there any way to reverse this process? If we were to start with huge graph GN, is there any way would could extract the 'kernel graph' G?
I haven't heard of the "gizmo" method, but these kinds of transformations between graphs and formulas are typically reversible, and if so, reconstructing G1 from GN would be doable. I don't see the point in doing this though.
@@albertrmeyer2336 Sorry - the gizmo method is what I was referring to as the method you present in your other sat to 3color video, where you replace each logic gate of the circuit with a 'graph gadget' and hook the gadgets together to produce the graph whose colorability is equivalent to the satifiability of the circuit/proposition. I heard the gadgets referred to as gizmos elsewhere and that's the name the stuck in my mind. It seems to me that if you could reverse the process and get graph G1 from graph GN that this might be a process whereby we could 'compress' arbitrary graphs - if they are 'compressible' in this sense. The reason I'm interested in this is because I'm looking into graphs as possible compressed representations of shapes (for computer graphics). Thanks for your reply, and for the excellent videos BTW.
@@aaronkambeitz4875 The G1...GN sequence of graphs will be very special, and the ability to recover G1 from GN is unlikely to be relevant to "compressing" general graphs. I have seen some recent results on finding small subnets of large neural nets that serve about equally as well at pattern classification; I don't have references handy, but googling might lead you to the relevant research.
@@albertrmeyer2336 Thank you sir!
Was someone snoring ?
Gg
Ghdjf
Tisifhdu