The Convenience of Tilings
Peter van Emde Boas

Abstract:
Tiling problems provide for a very simple and transparent mechanism for 
encoding machine computations. This gives rise to rather simple master 
reductions showing various versions of the tiling problem complete for 
various complexity classes. We investigate the potential for using these 
tiling problems in subsequent reductions showing hardness of the 
combinatorial problems that really matter.
We ilustrate our approach by means of three examples: a short reduction chain 
to the Knapsack problem followed by a Hilbert 10 reduction using similar 
ingredients. Finally we reprove the Deterministic Exponential Time lowerbound 
for satisfiability in Propositional Dynamic Logic.
The resulting reductions are relatively simple; they do however infringe on 
the principle of orthogonality of reductions since they abuse extra structure 
in the instances of the problems reduced from which results from the fact 
that these instances were generated by a master reduction previously.