imported>Rolf acker: cite-conference-Vorlagenfehler beseitigt

2023-03-16T04:27:03Z

cite-conference-Vorlagenfehler beseitigt

Neue Seite

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 Ronald da Silva Meyer|Albert Meyer]] aus dem Jahr 1969 zurück<ref name="MM">
{{cite conference
| conference = ACM Symposium on Theory of Computing
| publisher = Association for Computing Machinery, New York, NY, USA
| location = Marina del Rey, California, USA
| title = Classes of Computable Functions Defined by Bounds on Computation: Preliminary Report
| last1 = McCreight
| first1 = E. M.
| last2 = Meyer
| first2 = A. R.
| year = 1969
| book-title = Proceedings of the First Annual ACM Symposium on Theory of Computing
| series = STOC '69
| pages = 79–88
| isbn = 9781450374781
| doi = 10.1145/800169.805423
| language = en
}}</ref>
und sagt Folgendes aus: Ist eine Liste von Zeitschranken <math>t_1,t_2,\dots</math> mit <math>t_{i+1} \ge t_i</math> 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 <math>t_i</math> berechenbar ist. Das Theorem lässt sich insbesondere zur Bildung von [[Komplexitätsklasse]]n einsetzen und bildet damit eine der Grundlagen zur Formulierung der [[Komplexitätstheorie#Hierarchiesätze|Hierarchiesätze]]. Beispielsweise folgt aus dem Theorem, dass Funktionen, die deterministisch in [[Polynomialzeit]] berechenbar sind, eine Komplexitätsklasse bilden.

In Kap. 12.6 der ersten Ausgabe von 1979 des Lehrbuchs von Hopcroft und Ullman<ref name="HU">
{{cite book
| last1 = Hopcroft
| first1 = John E.
| last2 = Ullman
| first2 = Jeffrey D.
| title = Introduction to Automata Theory, Languages, and Computation
| url = https://archive.org/details/introductiontoau00hopc
| publisher = Addison-Wesley
| edition = 1
| year = 1979
| isbn = 0-201-02988-X
| language = en
}}</ref>
finden sich Varianten des Union-Theorems. In neueren Auflagen fehlt dieses Kapitel.

== Einzelnachweise ==
<references />

[[Kategorie:Komplexitätstheorie]]

Union-Theorem - Versionsgeschichte

imported>Rolf acker: cite-conference-Vorlagenfehler beseitigt