Quel est co-chose?

Question

Qu'est-ce que la notation moyenne co- lorsque préfixer co-NP, co-RE (récursivement dénombrable), ou co-CE (récursivement dénombrable)?

Answer 1

Souvent, dans la terminologie mathématique, le préfixe co - fait référence à un double dans un certain sens. Pour les classes de complexité et calculabilité, le préfixe co - a une signification fixe: si X est une classe de problèmes de décision, puis co-X la classe des problèmes dont complément dans X . Autrement dit, si le problème « ne cet objet ont la propriété $ P $ » est dans X , le problème « ne cet objet a la propriété $ \ neg P $? » Est en co-X .

Par exemple, RE est la classe de problèmes semi-décidables , qui est, pour les problèmes qui il y a une machine de Turing qui peut vérifier une réponse positive. Co-RE est la classe des problèmes pour lesquels il existe une machine de Turing qui peut vérifier une réponse négative. est le problème de l'arrêt (de manière intuitive, vous pouvez vérifier qu'une arrête la machine de Turing en exécutant à la fin, mais si la machine fonctionne toujours, vous ne serez jamais sûr) Un problème bien connu qui est RE, mais pas en co-RE .

NP est la classe des problèmes pour lesquels une solution peut être vérifiée en temps polynomial; de manière équivalente, NP est la classe des problèmes qui peuvent être résolus par une machine de Turing non-déterministe en temps polynomial. Co-NP est la classe des problèmes pour lesquels l'absence d'une solution peut être prouvée dans le temps polynomiale. On ne sait pas si le texte $ \ {NP} = \ texte {co-NP} $.

Answer 2

Dans la partie plus algébrique de la science informatique théorique, des moyens co-double, comme dans Gilles' réponse , mais il a une interprétation très précise. Si le concept d'intérêt (disons un produit ) est officialisé dans la théorie de la catégorie, le double ( coproduits ) sont les mêmes concepts avec les flèches allant dans le sens opposé .

Un exemple simple (résumé) est l'idée d'une algèbre , qui, pour un foncteur $ F $, est une paire $ \ langle S, \ alpha: FS \ S \ rangle $. Algèbres sont importants dans la science informatique pour la modélisation des types de données. Le double d'une algèbre est cogèbre , qui est une paire $ \ langle S, \ alpha: S \ FS \ rangle $. Coalgèbres sont importants pour les systèmes de modélisation.

Qu'est-ce qui est arrivé quand on dualisée? Eh bien, la flèche $ FS \ S $ a été inversée, l'obtention de S $ \ FS $.

L'une des choses cool sur cette idée est que toute la théorie qui fonctionne pour un concept fonctionne pour le concept dual, où toutes les flèches sont inversées.