Complemento (complejidad)

Por ejemplo, un problema importante es si un número es primo. Su complemento es para determinar si un número es compuesto (un número que no es primo). 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.[4] La operación del complemento es una involución, lo que significa que se deshace a sí misma, o el complemento del complemento es el problema original.

Puede generalizarse este hecho al complemento de una clase de complejidad, llamada clase de complemento, que es el conjunto de complementos de cada problema en la clase.[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.

Se dice que una clase está cerrada bajo complemento si el complemento de cualquier problema en la clase todavía está en la clase.[6] Debido a que hay reducciones de Turing de cada problema a su complemento, cualquier clase que se cierra bajo las reducciones de Turing se cierra bajo el complemento. Cualquier clase que se cierra bajo complemento es igual a su clase de complemento. 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).[7]

El cierre de cualquier clase de complejidad bajo las reducciones de Turing es un superconjunto de esa clase que se cierra bajo el complemento. El cierre bajo complemento es la clase más pequeña de este tipo. Si una clase se cruza con su complemento, se obtiene un subconjunto (posiblemente vacío) que se cierra bajo el complemento.

Cada clase de complejidad determinista (DSPACE(f(n)), DTIME(f(n)) para todas las f(n)) se cierra bajo el complemento,[8] porque simplemente se puede agregar un último paso para el algoritmo que invierte la respuesta. Esto no funciona para las clases de complejidad no deterministas, porque si existen caminos de cálculo que aceptan y caminos que rechazan, y todos los caminos invierten su respuesta, todavía habrá caminos que aceptan y caminos que rechazan — en consecuencia, la máquina acepta en ambos casos.

Algunos de los resultados de complejidad más sorprendentes analizados hasta la fecha mostraron que las clases de complejidad NL y SL están de hecho cerradas bajo el complemento, mientras que antes se creía ampliamente que no lo estaban (véase teorema de Immerman-Szelepcsényi). Esto último se ha vuelto menos sorprendente ahora que se sabe que SL es igual a L, que es una clase determinista.

Cada clase que es baja por sí misma se cierra bajo complemento.