Two fundamental papers in computational complexity theory and the theory of formal languages are very short:
Neil Immerman, Nondeterministic space is closed under complementation, SIAM Journal on Computing 17(5), 935–938, 1988 (four pages);
Róbert Szelepcsényi, The method of forcing for nondeterministic automata, Bulletin of the EATCS 33, 96–100, 1987 (five pages).
Both papers independently prove what is now called the Immerman-Szelepcsényi theorem, i.e., that nondeterministic space complexity classes are closed under complement, and in particular that context-sensitive languages are closed under complement. The authors shared the Gödel Prize in 1995 for their result.
I’ve never read Szelepcsényi’s version, but Immerman’s is so short and sweet that I found it hard to believe at first that it actually works as a proof of such an important theorem.
