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 mit 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 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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.