4 ms·
Any Monotone Boolean Function Can Be Realized by Interlocked Polygons (2010)
- seg_lol 6y agoErik Demaine has a wonderful collection of videos on youtube around Geometry, Algorithms and their intersection. The Geometry of Origami https://www.youtube.com/watch?v=oUnNkHGXefA https://www.youtube.com/watch?v=oUnNkHGXefA
- TheNewAndy 6y agoSee also: https://arxiv.org/pdf/1203.3602.pdf https://arxiv.org/pdf/1203.3602.pdf You can also encode any monotone boolean function by hanging a picture on the wall on N nails (one nail per variable). e.g. a "normal" hanging of a picture on two nails would encode an AND gate (it only falls if both nails are removed). But by twisting the string the right way, you can make it encode an OR gate (so it falls if either nail is removed).
- TheNewAndy 6y agoIf you enjoy this kind of paper, then I highly recommend this book: https://www.routledge.com/Games-Puzzles-and-Computation/Hearn-Demaine/p/book/9781568813226 https://www.routledge.com/Games-Puzzles-and-Computation/Hear... It has a huge number of examples of how to build similar gadgets using lots of different kinds of games.
- TheNewAndy 6y ago... and from memory, it does include sliding tile puzzles like from this paper.
- deleted 6y ago[deleted]
- abeppu 6y agoIs there some lemma relating monotonicity of a boolean function with planarity of some graph?
- klyrs 6y agoFigure 7, the cross gadget, resolves that issue rather tidily. This is a very nice, constructive proof where the pictures tell much of the story and are responsible for at least a third of the 4-page paper. Give it a read!