Aquí el dominio del complemento es el conjunto de todos los números enteros superiores a uno.
[3] Existe una reducción de Turing desde cada problema hasta su complemento.
[5] Si una clase se llama C, su complemento se denomina convencionalmente co-C. Nótese que esto no es el complemento de la clase de complejidad en sí misma como un conjunto de problemas, que contendría muchos más problemas.
Sin embargo, bajo la reducción de muchos a uno, se cree que muchas clases importantes, especialmente los problemas de dificultad NP, son distintas de sus clases complementarias (aunque esto no se ha probado).
El cierre bajo complemento es la clase más pequeña de este tipo.