What is co-something?

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

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}$.

StackExchange Computer Science Q#1370, answer score: 11