On the parallel complexity of loops. Selected references Ashok K. Chandra, Dexter C. Kozen, and Larry J. Stockmeyer. Stephen A. Cook. A taxonomy of problems with fast parallel algorithms. Oscar H. Ibarra, Tao Jiang, Jik H. Chang, and Bala Ravikumar.
Nondeterministic space is closed under complementation.
Neil D. Jones and William T. Laaser. Complete problems for deterministic polynomial time. Jan van Leeuwen and Maurice Nivat. Efficient recognition of rational relations. Walter L. Ruzzo.