reductions as computational gadgets

The chapter on NP-completeness in Moore and Mertens, The Nature of Computation (2011) does a reduction from circuit SAT to the tiling problem on polyomino regions. They are a bit hand-wavy in the text about the details, but they create tiling gadgets that represent true and false values on wires, AND gates and NOT gates, that have different tilings depending on the input and output tilings, and a gadget that requires that the tile-circuit evaluate to True. So if there is a tiling on the region, the corresponding circuit is satisfiable. There is a delightful figure:

The punch line when proving poly-time reductions is that the problem you’re reducing to is NP-complete, and therefore it’s hard to solve. But when the problem we are reducing from happens to be something like circuit-SAT where problem instances are close to a natural model of computation, our reduction highlights that what we usually see as a problem for some other algorithm, like tiling, can also be worked into a computational model of its own. Any problem in NP can be used to build toy computers, and some of those toys might even be fun to play with. These are not earth-shattering insights, just the usual pieces sliding more pleasingly into place.