Теорема союза

Теорема объединения является результатом 60-х годов в теории сложности вычислений . Он был опубликован в 1969 году Эд МакКрайт и Альберт Мейер .

Первоначально это указано для общих классов сложности Blum , но наиболее актуально для DTIME , NTIME , DSPACE или NSPACE, как указано в гл. 12.6 первого издания 1979 г. учебника Хопкрофта и Ульмана. Однако эта глава была удалена из новых изданий.

Теорема о временной сложности примерно гласит следующее. Дан список монотонно возрастающих функций, ограниченных по времени. $t_{1},t_{2},\dots$ где $t_{i+1}\geq t_{i}$ для $i\in \mathbb {N} _{>0}$, существует ограниченная по времени функция $t$ такая, что задача вычислима за время, ограниченное $t$ тогда и только тогда, когда существует $i$ такая, что задача вычислима за время, ограниченное $t_{i}$.

Теорему можно применить, чтобы показать, что классы сложности, такие как P, четко определены. Вместе с теоремой об ускорении , теоремой о разрыве и теоремами об иерархии времени и пространства она является основой иерархий в теории сложности .