Both theorems use the notion of a [[constructible function|time-constructible function]]. A [[function (mathematics)|function]] ''<math>f'' : '''\mathbb{N''' → '''}\rightarrow\mathbb{N'''}</math> is time-constructible if there exists a deterministic [[Turing machine]] such that for every ''<math>n'' \in '''\mathbb{N'''}</math>, if the machine is started with an input of ''n'' ones, it will halt after precisely ''<math>f''(''n'')</math> steps. All [[polynomial]]s with non-negative integral coefficients are time-constructible, as are exponential functions such as 2<supmath>''2^n''</supmath>.
