En la teoría de la complejidad computacional , el complemento de un problema de decisión es el problema de decisión que resulta de invertir las respuestas de sí y no . [1] De manera equivalente, si definimos los problemas de decisión como conjuntos de cadenas finitas, entonces el complemento de este conjunto sobre algún dominio fijo es su problema de complemento. [2]
Por ejemplo, un problema importante es si un número es primo . Su complemento sirve 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 enteros que exceden a uno. [3]
Hay una reducción de Turing de cada problema a su problema complementario. [4] La operación del complemento es una involución , lo que significa que "se deshace", o el complemento del complemento es el problema original.
Se puede generalizar esto al complemento de una clase de complejidad , llamada clase de complemento , que es el conjunto de complementos de cada problema de la clase. [5] Si una clase se llama C , su complemento se etiqueta convencionalmente como co-C . Observe que este 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 desde cada problema hasta su complemento, cualquier clase que esté cerrada bajo las reducciones de Turing se cierra bajo el complemento. Cualquier clase que esté cerrada bajo complemento es igual a su clase de complemento. Sin embargo, en las reducciones de muchos uno , se cree que muchas clases importantes, especialmente NP , son distintas de sus clases complementarias (aunque esto no se ha probado). [7]
El cierre de cualquier clase de complejidad bajo reducciones de Turing es un superconjunto de esa clase que está cerrado bajo complemento. El cierre debajo del complemento es el más pequeño de su clase. Si una clase se cruza con su complemento, obtenemos un subconjunto (posiblemente vacío) que está cerrado bajo complemento.
Cada clase de complejidad determinista ( DSPACE (f (n)), DTIME (f (n)) para todo f (n)) se cierra bajo complemento, [8] porque uno puede simplemente agregar un último paso al algoritmo que invierte la respuesta . Esto no funciona para clases de complejidad no deterministas, porque si existen rutas de cálculo que aceptan y rutas que rechazan, y todas las rutas invierten su respuesta, todavía habrá rutas que aceptan y rutas que rechazan; en consecuencia, la máquina acepta en ambos casos.
Algunos de los resultados de complejidad más sorprendentes mostrados hasta la fecha mostraron que las clases de complejidad NL y SL están de hecho cerradas bajo complemento, mientras que antes se creía ampliamente que no lo eran (ver teorema de Immerman-Szelepcsényi ). Esto último se ha vuelto menos sorprendente ahora que sabemos que SL es igual a L , que es una clase determinista.
Cada clase que es baja por sí misma está cerrada bajo complemento.
Referencias
- ^ Itô, Kiyosi (1993), Diccionario enciclopédico de matemáticas, volumen 1 , MIT Press, p. 269, ISBN 9780262590204.
- ^ Schrijver, Alexander (1998), Teoría de la programación lineal y entera , Serie Wiley en Matemáticas discretas y optimización, John Wiley & Sons, p. 19, ISBN 9780471982326.
- ^ Homero, Steven; Selman, Alan L. (2011), Computabilidad y Teoría de la Complejidad , Textos en Ciencias de la Computación, Springer, ISBN 9781461406815.
- ^ Singh, Arindama (2009), Elementos de la teoría de la computación , Textos en informática, Springer, Ejercicio 9.10, p. 287, ISBN 9781848824973.
- ^ Bovet, Daniele; Crescenzi, Pierluigi (1994), Introducción a la teoría de la complejidad , Prentice Hall International Series in Computer Science, Prentice Hall, págs. 133-134, ISBN 9780139153808.
- ^ Vollmer, Heribert (1999), Introducción a la complejidad de los circuitos: un enfoque uniforme , Textos en informática teórica. Una serie EATCS, Springer, pág. 113, ISBN 9783540643104.
- ^ Pruim, R .; Wegener, Ingo (2005), Teoría de la complejidad: exploración de los límites de los algoritmos eficientes , Springer, p. 66, ISBN 9783540274773.
- ^ Ausiello, Giorgio (1999), Complejidad y aproximación: problemas de optimización combinatoria y sus propiedades de aproximación , Springer, p. 189, ISBN 9783540654315.