Complemento (complejidad)
En 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 sí y no.[1] De manera equivalente, si se definen 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]
Características
editarPor 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.
Referencias
editar- ↑ Itô, Kiyosi (1993), Encyclopedic Dictionary of Mathematics, Volume 1, MIT Press, p. 269, ISBN 9780262590204..
- ↑ Schrijver, Alexander (1998), Theory of Linear and Integer Programming, Wiley Series in Discrete Mathematics & Optimization, John Wiley & Sons, p. 19, ISBN 9780471982326..
- ↑ Homer, Steven; Selman, Alan L. (2011), Computability and Complexity Theory, Texts in Computer Science, Springer, ISBN 9781461406815..
- ↑ Singh, Arindama (2009), Elements of Computation Theory, Texts in Computer Science, Springer, Exercise 9.10, p. 287, ISBN 9781848824973..
- ↑ Bovet, Daniele; Crescenzi, Pierluigi (1994), Introduction to the Theory of Complexity, Prentice Hall International Series in Computer Science, Prentice Hall, pp. 133-134, ISBN 9780139153808..
- ↑ Vollmer, Heribert (1999), Introduction to Circuit Complexity: A Uniform Approach, Texts in Theoretical Computer Science. An EATCS Series, Springer, p. 113, ISBN 9783540643104..
- ↑ Pruim, R.; Wegener, Ingo (2005), Complexity Theory: Exploring the Limits of Efficient Algorithms, Springer, p. 66, ISBN 9783540274773..
- ↑ Ausiello, Giorgio (1999), Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer, p. 189, ISBN 9783540654315..
Datos: Q4249733
