hierarchy (mathematics)

Information about hierarchy (mathematics)

In mathematics, a hierarchy is a preorder, i.e. an ordered set. The term is used to stress a natural hierarchical relation among the elements. In particular, it is the preferred terminology for posets whose elements are classes of objects of increasing complexity. In that case, the preorder defining the hierarchy is the class-containment relation. Containment hierarchies are thus special cases of hierarchies.

Related terminology

Individual elements of a hierarchy are often called levels and a hierarchy is said to be infinite if it has infinitely many distinct levels but said to collapse if it has only finitely many distinct levels.

Example

In theoretical computer science, the time hierarchy is a classification of decision problems according to the amount of time required to solve them.

See also

Mathematics (colloquially, maths or math) is the body of knowledge centered on such concepts as quantity, structure, space, and change, and also the academic discipline that studies them. Benjamin Peirce called it "the science that draws necessary conclusions".
..... Click the link for more information.
In mathematics, especially in order theory, preorders are binary relations that satisfy certain conditions. For example, all partial orders and equivalence relations are preorders. The name quasiorder is also common for preorders.
..... Click the link for more information.
hierarchy (in Greek: Ἱεραρχία, derived from ἱερός — hieros, 'sacred', and
..... Click the link for more information.
partially ordered set (or poset) formalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that describes, for certain pairs of elements in the set, the requirement that one
..... Click the link for more information.
In set theory and its applications throughout mathematics, a class is a collection of sets (or sometimes other mathematical objects) that can be unambiguously defined by a property that all its members share.
..... Click the link for more information.
Complexity in general usage is the opposite of simplicity. Complexity in specific usage is the opposite of independence, while complication is the opposite of simplicity.
..... Click the link for more information.
A containment hierarchy is a hierarchical collection of strictly nested sets. Each entry in the hierarchy designates a set such that the previous entry is a strict superset, and the next entry is a strict subset.
..... Click the link for more information.
Theoretical computer science is the collection of topics of computer science that focuses on the more abstract, logical and mathematical aspects of computing, such as the theory of computation, analysis of algorithms and semantics of programming languages.
..... Click the link for more information.
In computational complexity theory, the time hierarchy theorems are important statements that ensure the existence of certain "hard" problems which cannot be solved in a given amount of time.
..... Click the link for more information.
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem.
..... Click the link for more information.
In mathematical logic and descriptive set theory, the analytical hierarchy is a higher type analogue of the arithmetical hierarchy. It thus continues the classification of sets by the formulas that define them.
..... Click the link for more information.
In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene hierarchy classifies certain sets based on the complexity of formulas that define them. Any set that receives a classification is called arithmetical.
..... Click the link for more information.
In mathematical logic, the Borel hierarchy is a stratification of the Borel algebra generated by the open subsets of a Polish space; elements of this algebra are called Borel sets.
..... Click the link for more information.
In descriptive set theory, Wadge degrees are levels of complexity for sets of reals and more comprehensively, subsets of any given topological space. Sets are compared by continuous reductions. The Wadge hierarchy is the structure of Wadge degrees.
..... Click the link for more information.
Within the field of computer science, specifically in the area of formal languages, the Chomsky hierarchy (occasionally referred to as Chomsky–Schützenberger hierarchy) is a containment hierarchy of classes of formal grammars.
..... Click the link for more information.
In set theory, the difference hierarchy over a pointclass is a hierarchy of larger pointclasses generated by taking differences of sets. If Γ is a pointclass, then the set of differences in Γ is . In usual notation, this set is denoted by 2-Γ.
..... Click the link for more information.
In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines.

Definitions

There are multiple equivalent definitions of the classes of the polynomial hierarchy.
..... Click the link for more information.

This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.