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 mathematics_logic_statistics 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. Informally, it means that if the answer to a problem instance is 'yes', then there is some procedure that takes finite time to determine this, and this procedure never falsely reports 'yes' when the true answer is 'no'. However, when the true answer is 'no', the procedure is not required to halt; it may go into an "infinite loop" for some 'no' cases.

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. Similarly, co-RE is the set of all languages that are complements of a language in RE. In a sense, co-RE contains languages of which membership can be disproved in a finite amount of time, but proving membership might take forever.

For Co-RE-complete, the abstraction is narrower than the article's general subject matter: a positive case must preserve Such a procedure is sometimes called a semi-algorithm, to distinguish it from an algorithm, defined as a complete solution to a decision problem. Retaining only the name, a familiar example, or a downstream effect is insufficient. The specialist roles and tests remain anchored in mathematics_logic_statistics, which is why this identity is domain-specific rather than prime.

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.

Structural Signature¶

Sig role-phrases:

Defining carrier — 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).
Constitutive relation — 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.
Operating condition — 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 that are accepted (there is an order of execution that will eventually get to every execution step because there are countably many ordered pairs of inputs and steps).
Recognition evidence — 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.
Admissible variation — Each member of RE is a recursively enumerable set and therefore a Diophantine set.
Characteristic consequence — 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 the string is enumerated.
Failure boundary — The set of recursive languages (R) is a subset of both RE and co-RE.

What It Is Not¶

Not the whole field of mathematics_logic_statistics. The node requires the specific identity stated by 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.
Not an over-broad reading. However, when the true answer is 'no', the procedure is not required to halt; it may go into an "infinite loop" for some 'no' cases.
Not an over-broad reading. These are the set of languages for which neither membership nor non-membership can be proven in a finite amount of time, and contain all other languages that are not in either RE or co-RE.
Not an over-broad reading. Generally, no constraint is placed on the reductions used except that they must be many-one reductions.
Not automatically Entscheidungsproblem. Retrieval proximity does not establish equivalence; the two identities must be compared by carrier, operation, and failure boundary.

Scope of Application¶

Co-RE-complete applies literally inside mathematics_logic_statistics wherever the source-defined carrier and relation can be established. Its documented habitats include:

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 the string is enumerated.
Relations to other classes. The set of recursive languages (R) is a subset of both RE and co-RE.

Outside mathematics_logic_statistics, the name should be retained only when these same operational conditions survive; otherwise the comparison belongs to the broader parent Classification or should be marked as analogy.

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. The strongest recognition evidence in the frozen account is: 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. A report should distinguish that evidence from a proxy, consequence, or common implementation. It should also state the qualification However, when the true answer is 'no', the procedure is not required to halt; it may go into an "infinite loop" for some 'no' cases. so that a reader can reproduce the classification rather than infer it from topical resemblance.

Manages Complexity¶

Co-RE-complete compresses multiple mathematics_logic_statistics 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 enumerates all accepted inputs, another machine that takes in a string can run E and accept if the string is enumerated. This compression makes cases comparable while leaving parameters, conventions, exceptions, and evidential quality explicit. It is lossy by design: local history and implementation details may be omitted only when they do not alter the defining relation.

Abstract Reasoning¶

Type the carrier. Identify the mathematics_logic_statistics 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 that are accepted (there is an order of execution that will eventually get to every execution step because there are countably many ordered pairs of inputs and steps).
Demand recognition evidence. 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.
Test variation. Change an implementation or setting while preserving each member of RE is a recursively enumerable set and therefore a Diophantine set.
Run the collapse test. Remove the defining operation; if the label still seems equally apt, only a topic or correlate was retained.
Reduce cautiously. When the specialist conditions cannot be carried, route the residual comparison to Classification.

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.

Examples¶

Canonical¶

However, when the true answer is 'no', the procedure is not required to halt; it may go into an "infinite loop" for some 'no' cases. This case is canonical because it supplies a concrete carrier and lets the defining relation be checked rather than merely named.

Mapped back: carrier → the entities in the documented case; operation → Such a procedure is sometimes called a semi-algorithm, to distinguish it from an algorithm, defined as a complete solution to a decision problem; recognition evidence → 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

Applied / In Practice¶

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). The applied case shows how the identity is used under a second setting or qualification while keeping the same operative relation.

Mapped back: changed setting → Equivalent definition; invariant → Such a procedure is sometimes called a semi-algorithm, to distinguish it from an algorithm, defined as a complete solution to a decision problem; boundary → the case exits the class when however, when the true answer is 'no', the procedure is not required to halt; it may go into an "infinite loop" for some 'no' cases

Structural Tensions¶

T1 — Stable identity versus admissible variation. However, when the true answer is 'no', the procedure is not required to halt; it may go into an "infinite loop" for some 'no' cases. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Which changes preserve the defining relation, and which replace it?

T2 — Recognition versus proxy. These are the set of languages for which neither membership nor non-membership can be proven in a finite amount of time, and contain all other languages that are not in either RE or co-RE. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Does the cited evidence establish the identity or only a correlated sign?

T3 — Definition versus implementation. Generally, no constraint is placed on the reductions used except that they must be many-one reductions. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Is the observed implementation constitutive, optional, or merely common?

T4 — Scope versus overextension. In January 2020, a preprint announced a proof that RE was equivalent to the class MIP* (the class where a classical verifier interacts with multiple all-powerful quantum provers who share entanglement); a revised, but not yet fully reviewed, proof was published in Communications of the ACM in November 2021. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Can every claimed application fill the same typed roles without metaphor?

T5 — Transfer versus domain accent. 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). The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Does the receiving case instantiate Co-RE-complete literally, co-instantiate Classification, or only resemble it?

T6 — Autonomy versus reduction. 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. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: What does Co-RE-complete distinguish that the broader parent Classification leaves together?

Structural–Framed Character¶

Co-RE-complete is structural-leaning. Its structural side is the repeatable organization summarized by 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. Its framed side is the mathematics_logic_statistics vocabulary that fixes the carrier, evidence, exceptions, and admissible transformations.

Evaluative weight: the identity can be stated descriptively even when applications carry practical stakes. Human-practice dependence: the source-grounded carrier determines whether the relation exists independently or is constituted by a practice. Institutional origin: disciplinary conventions stabilize the name and test. Vocabulary portability: 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 that are accepted (there is an order of execution that will eventually get to every execution step because there are countably many ordered pairs of inputs and steps). Import versus recognition: literal transfer requires the same mechanism; shape alone is analogy.

Its portable skeleton is Classification. Its character: a recurring specialist identity whose thin organization can be abstracted, while its operational meaning remains domain-bound.

Structural Core vs. Domain Accent¶

What is skeletal. 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. The stable skeleton is the typed relation expressed in that definition and the entry's recognition and collapse tests. The source identifies these operative conditions: 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). 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. It further constrains recognition and variation through: 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 that are accepted (there is an order of execution that will eventually get to every execution step because there are countably many ordered pairs of inputs and steps). 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.

What is domain-bound. mathematics logic statistics supplies the operative entities, technical vocabulary, warrants, and exceptions that make Co-RE-complete literal. Its documented scope includes the condition that Generally, no constraint is placed on the reductions used except that they must be many-one reductions. Another bounded application condition is that By Rice's theorem, deciding membership of a in any nontrivial subset of the set of partial recursive functions is RE-hard. These are not decorative examples; they determine which carrier and evidence can fill the abstraction's roles.

Why no parent is asserted. Removing those specialist details does not currently yield one live catalog node that is a necessary genus for every instance. The entry is therefore approved as unparented rather than attached by topical resemblance. Its collapse evidence remains specific—Each member of RE is a recursively enumerable set and therefore a Diophantine set.—and future graph densification may discover a defensible relation only if it preserves that boundary.

This entry is a kind of Computational problem.

Approved unparented node. No current live node supplies a defensible necessary genus or structural prerequisite for Co-RE-complete. The reviewed identity 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. The accelerated suggestion was declined because topical or lexical similarity does not establish hierarchy; the node is admitted without a parent pending later graph densification.
Related reasoning operations. Evidence, representation, comparison, classification, transformation, or evaluation may participate in particular cases, but participation does not make any one of them a necessary parent of every instance.

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

Not to Be Confused With¶

Classification. The parent omits the specialist differentia. Tell: Can the case establish Such a procedure is sometimes called a semi-algorithm, to distinguish it from an algorithm, defined as a complete solution to a decision problem?
Entscheidungsproblem. The historical decision problem asking for an algorithm that determines whether any first-order logical sentence is valid, proved impossible by Church and Turing. Tell: Which entry's carrier, operation, and failure condition are satisfied?
Decidability Computability. A class of yes/no questions admits a finite procedure that always terminates with the correct answer. Tell: Which entry's carrier, operation, and failure condition are satisfied?
Complete (complexity). Complete (complexity) denotes notion of the "hardest" or "most general" problem in a complexity class in computing and information systems. Tell: Which entry's carrier, operation, and failure condition are satisfied?
A measurement, proxy, or consequence. Those may provide evidence without being the identity. Tell: Would Co-RE-complete remain present if the detector or downstream effect changed?
A metaphorical analogue. A similar shape outside mathematics_logic_statistics lacks the specialist mechanism. Tell: Do the native roles transfer literally, or only the parent Classification?

References¶

Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/RE_(complexity) (revision 1365167192).
Preserved source candidate: https://archive.org/details/logicalgorithmsw0000korf
Preserved source candidate: https://archive.org/details/logicalgorithmsw0000korf/page/89

The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.