 RE (complexity)

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.^{[1]} Informally, it means that if the answer is 'yes', then there is some procedure which takes finite time to determine this. On the other hand, if the answer is 'no', the machine might never halt. 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).
Similarly, coRE is the set of all languages that are complements of a language in RE. In a sense, coRE contains languages of which membership can be disproved in a finite amount of time, but proving membership might take forever.
Each member of RE is a recursively enumerable set and therefore a Diophantine set.
Contents
Relations to other classes
The set of recursive languages (R) is a subset of both RE and coRE.^{[2]} In fact, it is the intersection of those two classes:
REcomplete
REcomplete is the set of decision problems that are complete for RE. In a sense, these are the "hardest" recursively enumerable problems. All such problems are nonrecursive. Generally, no constraint is placed on the reductions used except that they must be manyone reductions.
Examples of REcomplete problems:
 Halting problem: Whether a program given a finite input finishes running or will run forever.
 By Rice's Theorem, deciding membership in any nontrivial subset of the set of recursive functions is REhard. It will be complete whenever the set is recursively enumerable.
 [Myhill 1955]^{[3]} has proven that all creative sets are REcomplete.
 The uniform word problem for groups or semigroups. [Indeed, the word problem for some individual groups is REcomplete.]
 Deciding membership in a general unrestricted formal grammar. [Again, certain individual grammars have REcomplete membership problem.]
 The validity problem for firstorder logic.
 Post correspondence problem: Given a finite set of strings, determine if there is a string that can be factored into a composition of the strings (allowing repeats) in two different ways.
 Determining if a Diophantine equation has any integer solutions.
coREcomplete
coREcomplete is the set of decision problems that are complete for coRE. In a sense, these are the complements of the hardest recursively enumerable problems.
Examples of coREcomplete problems:
 The Domino Problem for Wang tiles.
 The satisfiability problem for firstorder logic
See also
References
 ^ Complexity Zoo: Class RE
 ^ Complexity Zoo: Class coRE
 ^ Myhill, J. "Creative sets," Z. Math. Logik Grundlag. Math., v. 1, pp. 97–108.
Important complexity classes (more) Classes considered feasible Classes suspected to be infeasible UP • NP (NPcomplete · NPhard · coNP · coNPcomplete) • AM • PH • PP • #P (#Pcomplete) • IP • PSPACE (PSPACEcomplete)Classes considered infeasible Class hierarchies Families of complexity classes Categories: Complexity classes
Wikimedia Foundation. 2010.
Look at other dictionaries:
Complexity management — is a business methodology that deals with the analysis and optimization of complexity in enterprises. Effects of complexity pertain to all business processes along the value chain and hence complexity management requires a holistic approach.… … Wikipedia
Complexity theory and organizations — Complexity theory and organizations, also called complexity strategy or complex adaptive organization, is the use of Complexity theory in the field of strategic management and organizational studies. Contents 1 Overview 2 Early research 3 Later… … Wikipedia
compLexity — coL Логотип организации Страна … Википедия
Complexity theory and strategy — Complexity theory has been used extensively in the field of strategic management and organizational studies, sometimes called complexity strategy or complex adaptive organization on the internet or in popular press. Broadly speaking, complexity… … Wikipedia
Complexity (journal) — Discipline Complex Systems … Wikipedia
Complexity, Problem Solving, and Sustainable Societies — is a paper on energy economics by Joseph Tainter from 1996. Contents 1 Focus 1.1 Attempts 1.2 Requirement of knowledge 2 See … Wikipedia
Complexity theory — may refer to: The study of a complex system or complex systems Complexity theory and organizations, the application of complexity theory to strategy Complexity economics, the application of complexity theory to economics Chaos theory, the study… … Wikipedia
compLexity — Kürzel coL Manager Vereinigte Staaten Jason „1“ Lake … Deutsch Wikipedia
Complexity — Com*plex i*ty, n.; pl. {Complexities}. [Cf. F. complexit[ e].] 1. The state of being complex; intricacy; entanglement. [1913 Webster] The objects of society are of the greatest possible complexity. Burke. [1913 Webster] 2. That which is complex;… … The Collaborative International Dictionary of English
complexity — complexity. См. сложность генома. (Источник: «Англо русский толковый словарь генетических терминов». Арефьев В.А., Лисовенко Л.А., Москва: Изд во ВНИРО, 1995 г.) … Молекулярная биология и генетика. Толковый словарь.
complexity — index complication, confusion (turmoil), enigma, entanglement (confusion), imbroglio, impasse … Law dictionary