Union-Theorem

Union-Theorem

Das Union-Theorem ist ein Ergebnis aus der Frühzeit der Forschung zur Komplexitätstheorie. Es geht auf eine Veröffentlichung von Ed McCreight und Albert Meyer aus dem Jahr 1969 zurück und sagt Folgendes aus: Ist eine Liste von Zeitschranken t1,t2,... mit t_{i+1} \ge t_i für alle i gegeben, so existiert eine Zeitschranke t, so dass ein Problem genau dann in Zeit t berechenbar ist, wenn es für irgendein ti berechenbar ist. Das Theorem lässt sich insbesondere zur Bildung von Komplexitätsklassen einsetzen und bildet damit eine der Grundlagen zur Formulierung der Hierarchiesätze. Beispielsweise folgt aus dem Theorem, dass Funktionen, die deterministisch in Polynomialzeit berechenbar sind, eine Komplexitätsklasse bilden.


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Union of two regular languages — In formal language theory, and in particular the theory of nondeterministic finite state machines, it is known that the union of two regular languages is a regular language. This article provides a proof of that statement.TheoremFor any regular… …   Wikipedia

  • König's theorem (set theory) — For other uses, see König s theorem. In set theory, König s theorem (named after the Hungarian mathematician Gyula König) colloquially states that if the axiom of choice holds, I is a set, mi and ni are cardinal numbers for every i in I , and m i …   Wikipedia

  • Cantor–Bernstein–Schroeder theorem — In set theory, the Cantor–Bernstein–Schroeder theorem, named after Georg Cantor, Felix Bernstein, and Ernst Schröder, states that, if there exist injective functions f : A → B and g : B → A between the sets A and B , then there exists a bijective …   Wikipedia

  • Radon–Nikodym theorem — In mathematics, the Radon–Nikodym theorem is a result in functional analysis that states that, given a measurable space ( X , Sigma;), if a sigma finite measure nu; on ( X , Sigma;) is absolutely continuous with respect to a sigma finite measure… …   Wikipedia

  • Marriage theorem — In mathematics, the marriage theorem (1935), usually credited to mathematician Philip Hall, is a combinatorial result that gives the condition allowing the selection of a distinct element from each of a collection of subsets.Formally, let S = { S …   Wikipedia

  • Open mapping theorem (functional analysis) — In functional analysis, the open mapping theorem, also known as the Banach–Schauder theorem (named after Stefan Banach and Juliusz Schauder), is a fundamental result which states that if a continuous linear operator between Banach spaces is… …   Wikipedia

  • Carathéodory's extension theorem — See also Carathéodory s theorem for other meanings. In measure theory, Carathéodory s extension theorem proves that for a given set Ω, you can always extend a sigma; finite measure defined on R to the sigma; algebra generated by R , where R is a… …   Wikipedia

  • McNaughton's Theorem — In automata theory, McNaughton s theorem refers to a theorem that asserts that the set of ω regular languages is identical to the set of languages recognizable by deterministic Muller automata. [1] This theorem is proven by supplying an algorithm …   Wikipedia

  • Borel determinacy theorem — In descriptive set theory, the Borel determinacy theorem shows that any Gale Stewart game whose winning set is a Borel set is determined, meaning that one of the two players will have a winning strategy for the game. It was proved by Donald A.… …   Wikipedia

  • Nyquist–Shannon sampling theorem — Fig.1: Hypothetical spectrum of a bandlimited signal as a function of frequency The Nyquist–Shannon sampling theorem, after Harry Nyquist and Claude Shannon, is a fundamental result in the field of information theory, in particular… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”