Co-RE-complete¶

A decision problem is co-RE-complete when it belongs to co-RE and every problem in co-RE reduces to it under the declared reduction, making it maximally hard within that class.

Version: v1 · 2026-09-28 · History
Domain-specific #: 8509
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomain: Computability Theory → Computer Science & Software Engineering

Core Idea¶

Co-RE-complete is treated here as the recurring mathematicslogicstatistics identity summarized by this source-grounded definition: A decision problem is co-RE-complete when it belongs to co-RE and every problem in co-RE reduces to it under the declared reduction, making it maximally hard within that class. In computability theory and computational complexity theory, RE (recursively enumerable) is the class of decision problems for which a 'yes' answer can be verified by a Turing machine in a finite amount of time.

How would you explain it like I'm…

The Forever-Search Puzzle

Imagine the question 'Is this endless beach free of lost rings?' If there is a ring, you will find it someday and can say 'no'. But if the beach really is ring-free, you could search forever and never be sure. A Co-RE-complete question is the hardest question of this kind: if you had a magic answer to it, you could answer every other question of this kind too.

Hardest 'Only No Is Sure' Question

Computer scientists sort yes-or-no questions by what a computer can do with them. For some questions, whenever the true answer is 'no', a computer program can prove it in a finite amount of time, but when the answer is 'yes' the program may run forever without ever being sure. Those questions make up a group called co-RE. A co-RE-complete question is in that group and is the hardest one in it: every other co-RE question can be turned into it, so solving it would solve them all.

Hardest Problem in Co-RE

In computability theory, RE (recursively enumerable) is the class of yes/no problems where a Turing machine can confirm every 'yes' answer in finite time and never wrongly says 'yes', but may run forever on some 'no' instances. Such a procedure is called a semi-algorithm, as opposed to a full algorithm that always halts. co-RE is the class of complements of RE problems: 'no' answers can be confirmed in finite time, but confirming 'yes' might never finish. A problem is Co-RE-complete when it is in co-RE and every co-RE problem reduces to it under a stated kind of reduction. That makes it a hardest problem in co-RE: an algorithm for it would give one for every co-RE problem. Being merely hard or undecidable is not enough; both membership in co-RE and completeness under the declared reduction are required.

RE is the class of decision problems solvable by a semi-algorithm: a Turing machine that halts and accepts on every 'yes' instance, never accepts a 'no' instance, and may fail to halt on 'no' instances. co-RE consists of the complements of RE languages, so non-membership can be certified in finite time while membership may never be confirmed. A decision problem is Co-RE-complete when two conditions hold: it lies in co-RE, and every co-RE problem reduces to it under the declared reduction. Completeness makes it maximally hard within co-RE, and because of the reduction structure, deciding it would decide all of co-RE. The concept is narrower than 'undecidable': a problem can be undecidable yet lie outside co-RE, or be in co-RE without being complete. Its identity rests on the semi-algorithm notion and the explicit choice of reduction.

Scope of Application¶

RE-complete. Generally, no constraint is placed on the reductions used except that they must be many-one reductions.
RE-complete. By Rice's theorem, deciding membership of a in any nontrivial subset of the set of partial recursive functions is RE-hard.
Equivalent definition. Equivalently, RE is the class of decision problems for which a Turing machine can list all the 'yes' instances, one by one (this is what 'enumerable' means).
Equivalent definition. Each member of RE is a recursively enumerable set and therefore a Diophantine set.
Equivalent definition. To show this is equivalent, note that if there is a machine E that enumerates all accepted inputs, another machine that takes in a string can run E and accept if.

Clarity¶

A clear use of Co-RE-complete names the carrier, the operative relation, and the conditions under which the source treats the identity as present. The minimal definition is A decision problem is co-RE-complete when it belongs to co-RE and every problem in co-RE reduces to it under the declared reduction, making it maximally hard within that class.

Manages Complexity¶

Co-RE-complete compresses multiple mathematicslogicstatistics details into a stable diagnostic relation. The source shows both the central mechanism—in fact, it is the intersection of those two classes, because we can decide any problem for which there exists a recogniser and also a co-recogniser by simply interleaving them until one obtains a result.—and the practical consequence—to show this is equivalent, note that if there is a machine E that.

Abstract Reasoning¶

Type the carrier. Identify the mathematicslogicstatistics entities to which the claim applies.
State the relation. Use the source-grounded identity: A decision problem is co-RE-complete when it belongs to co-RE and every problem in co-RE reduces to it under the declared reduction, making it maximally hard within that class.
Check operation and conditions. Conversely, if a machine M accepts when an input is in a language, another machine can enumerate all strings in the language by interleaving simulations of M on every input and outputting strings.

Knowledge Transfer¶

Within the home domain. Knowledge about Co-RE-complete transfers literally when a new case preserves the same carrier type, relation, and recognition test. Generally, no constraint is placed on the reductions used except that they must be many-one reductions. By Rice's theorem, deciding membership of a in any nontrivial subset of the set of partial recursive functions is RE-hard. Beyond the home domain. No canonical parent is asserted for Co-RE-complete. An outside case receives the specialist name only when the same typed roles and rejection conditions can be filled literally; otherwise the comparison remains an analogy pending later graph densification.

Relationships to Other Abstractions¶

Current abstraction Co-RE-complete Domain-specific

Parents (1) — more general patterns this builds on

Co-RE-complete is a kind of Computational problem Domain-specific

Co-RE-complete denotes a decision problem complete for co-RE, not the complexity class itself.

Hierarchy path (1) — routes to 1 parentless root

Co-RE-complete → Computational problem → Function (Mapping)

Neighborhood in Abstraction Space¶

Co-RE-complete sits in a moderately populated region (40^th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Computation Models & Complexity Classes (37 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08