lovely things

I like beautiful reductions in the complexity theory.
Reduction technique looks like a particular kind of programing.
Programming: given a language L (Python, C++, Scheme), and a problem P (input of census information, train scheduling, web information retrieval), you have to produce a program P in L, which solves P.
CT Given a (often very simple) "programming language" L: Clique problem over graphs, Algebraic equations over GF[2], Finite State Automaton Non-Equivalence, a problem P (which is usually has much more involved definition then language L) , you have to produce a reduction R of P to L.

Many beatiful reduction are given in the following articles:

1. Some Simplified NP-Complete Graph Problems, M. R. Garey, D. S. Johnson and L. Stockmeyer, Theoretical Comp. Sci., 1 (1976), 237-267.
2. T.J. Schäfer, Complexity of some two-person perfect-information games,
   J.Comput. Syst. Science, 16 (1978) 185--225.

A few days ago Fortnow reminded about very beautiful results on alternating TM