Union theorem

The Union theorem is a result of the early research on complexity theory . It goes back to a publication by Ed McCreight and Albert Meyer from 1969 and says the following: If a list of time limits is given for all i, then there is a time limit t, so that a problem can be calculated in time t exactly, if it is predictable for anybody . The theorem can be used in particular for the formation of complexity classes and thus forms one of the bases for the formulation of the hierarchy statements . For example, it follows from the theorem that functions that are deterministic in ${\displaystyle t_{1},t_{2},\dots }$ ${\displaystyle t_{i+1}\geq t_{i}}$ ${\displaystyle t_{i}}$Polynomial times are computable, form a complexity class.