Any Monotone Boolean Function Can Be Realized by Interlocked Polygons (2010)

erikdemaine.org

76 points·ColinWright··6 comments

See also:

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).

If you enjoy this kind of paper, then I highly recommend this book:

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.

... and from memory, it does include sliding tile puzzles like from this paper.

Erik 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

Is there some lemma relating monotonicity of a boolean function with planarity of some graph?

Figure 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!

Reply on news.ycombinator.com