[Solved]: What is co-something?

Problem Detail: What does the notation co- mean when prefixing co-NP, co-RE (recursively enumerable), or co-CE (computably enumerable) ?

Asked By : Vanwaril

Answered By : Gilles

Often, in mathematical terminology, the prefix co- refers to a dual in some sense. For complexity and computability classes, the prefix co- has a fixed meaning: if X is a class of decision problems, then co-X is the class of problems whose complement is in X. That is, if the problem “does this object have the property $P$” is in X, then the problem “does this object have the property $neg P$?” is in co-X. For example, RE is the class of semi-decidable problems, that is, problems for which there is a Turing machine that can verify a positive answer. Co-RE is the class of problems for which there is a Turing machine that can verify a negative answer. A well-known problem that is in RE but not in co-RE is the halting problem (intuitively, you can verify that a Turing machine halts by running it to completion, but if the machine runs forever, you’ll never be sure). NP is the class of problems for which a solution can be verified in polynomial time; equivalently, NP is the class of problems that can be solved by a non-deterministic Turing machine in polynomial time. Co-NP is the class of problems for which the absence of a solution can be proved in polynomial time. It is not known whether $text{NP} = text{co-NP}$.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1370  Ask a Question  Download Related Notes/Documents