Simpler hardness proofs via gadget frameworks

In this thesis, I consider the general notion of a "gadget framework," which is roughly a family of hard problems that are useful as sources of reductions, where such reductions consist of implementations of a set of "gadgets," and especially when there is a notion of "simulation" between gadgets. I describe five gadget frameworks that I have helped invent or develop.

 

First, I present the history of the motion-planning gadgets framework, which was designed for proving hardness of problems like video games. Next, I describe two gadget frameworks which provide zero-player analogs of motion-planning gadgets: input/output gadgets, which represent a train moving through a network of rails and switches, and a framework designed for proving PSPACE-hardness of reversible deterministic systems. Fourth, I describe a gadget framework developed for Minesweeper and similar limited-information puzzles, which is used to prove hardness of three natural decision problems about such puzzles. Finally, I describe T-metacells, a framework for proving NP- and ASP- hardness of logic puzzles involving drawing a loop.