Revisou espaço : NL ⊆ SPACE e NL ⊆ P. Introduziu transdutores de espaço logarítmico e reducibilidade de espaço logarítmico. Definiu completude NL. Provou que é NL-completo e é NL-completo. Provou o teorema de Immerman-Szelepcsényi: NL = coNL.

Instrutor: Prof. Michael Sipser