Lo que es co-algo?

Question

¿Qué hace la media notación co- cuando el prefijo co-NP, co-RE (recursivamente numerable), o co-CE (computablemente enumerable)?

Answer 1

A menudo, en la terminología matemática, el prefijo co - se refiere a un dual en algún sentido. Para las clases de complejidad y de computabilidad, el prefijo co - tiene un significado fijo: si X es una clase de problemas de decisión, a continuación, co-X es la clase de problemas cuya complemento en X . Es decir, si el problema “no este objeto tiene la propiedad $ P $” es en X , entonces el problema “no este objeto tiene la propiedad $ \ neg P $?” es en co-X .

Por ejemplo, RE es la clase de problemas semi-decidibles , es decir, problemas para los cuales hay una máquina de Turing que puede verificar una respuesta positiva. Co-RE es la clase de los problemas para los cuales existe una máquina de Turing que puede verificar una respuesta negativa. Un problema bien conocido que está en RE, pero no en co-RE es el problema de la parada (de manera intuitiva, se puede verificar que una máquina de Turing se detiene mediante la ejecución hasta su finalización, pero si la máquina funciona siempre, que nunca estar seguro) .

NP es la clase de problemas para los que una solución se puede verificar en tiempo polinómico; equivalentemente, NP es la clase de problemas que pueden ser resueltos por una máquina de Turing no determinista en tiempo polinómico. Co-NP es la clase de problemas para los que la ausencia de una solución puede ser probadas en tiempo polinómico. No se sabe si $ \ text {NP} = \ text {co-NP} $.

Answer 2

En el lado más algebraica de la informática teórica, mediante co-dual, como en Gilles respuesta , pero tiene una interpretación muy precisa. Si el concepto de interés (digamos un producto ) se formaliza en la teoría de categorías, a continuación, el doble (un coproducto ) es el mismo concepto con las flechas que van en la dirección opuesta .

Un ejemplo simple (pero abstracta) es la idea de un álgebra , que, por un funtor $ F $, es un par $ \ S langle, \ alpha: FS \ a S \ rangle PS Álgebras son importantes en la informática para el modelado de tipos de datos. El dual de un álgebra es un coalgebra , que es un par $ \ langle S, \ alpha: S \ a FS \ rangle $. Coalgebras son importantes para el modelado de sistemas.

¿Qué pasó cuando dualizado? Bueno, la flecha FS $ \ $ a S se invirtió, obteniendo $ S \ a $ FS.

Una de las cosas interesantes acerca de esta idea es que toda la teoría que funciona para un concepto funciona para el concepto dual, donde todas las flechas se invierten.