194 Complexity — Exp Poly
194.1 Overview
This module introduces exponential-polynomial bounds, i.e. functions \(T : \mathbb {N} \to \mathbb {N}\) with \(T(n) \le 2^{K(n+1)^k}\) for some constants \(K, k\). It shows that such bounds contain the polynomials \(a(n+1)^d\) and the exponentials \(c \cdot 2^{n^e}\), are closed under domination, sums, products and polynomial reparametrization of the argument, and that every language decided within an exponential-polynomial time bound lies in \(\mathrm{EXP} = \bigcup _c \mathrm{DTIME}(2^{n^c})\) [AB09, Claim 2.4, §2.6.2].
194.2 Declarations
A function \(T : \mathbb {N} \to \mathbb {N}\) is exponential-polynomial if there exist constants \(K, k \in \mathbb {N}\) such that \(T(n) \le 2^{K(n+1)^k}\) for every \(n \in \mathbb {N}\).
For all natural numbers \(n\), \(k\) and \(k'\) with \(k \le k'\), we have \((n+1)^k \le (n+1)^{k'}\).
Let \(T, T' : \mathbb {N} \to \mathbb {N}\) satisfy \(T(n) \le T'(n)\) for every \(n\). If \(T'\) is exponential-polynomial, i.e. \(T'(n) \le 2^{K(n+1)^k}\) for all \(n\) and some constants \(K, k \in \mathbb {N}\), then \(T\) is exponential-polynomial as well.
For all constants \(c, e \in \mathbb {N}\), the function \(n \mapsto c \cdot 2^{n^e}\) is exponential-polynomial: there exist constants \(K, k \in \mathbb {N}\) such that \(c \cdot 2^{n^e} \le 2^{K(n+1)^k}\) for every \(n \in \mathbb {N}\).
For all constants \(a, d \in \mathbb {N}\), the function \(n \mapsto a(n+1)^d\) is exponential-polynomial: there exist constants \(K, k \in \mathbb {N}\) such that \(a(n+1)^d \le 2^{K(n+1)^k}\) for every \(n \in \mathbb {N}\).
Let \(T_1, T_2 : \mathbb {N} \to \mathbb {N}\) both be exponential-polynomial, i.e. each is bounded by \(2^{K(n+1)^k}\) for all \(n\) and some constants \(K, k \in \mathbb {N}\). Then the sum \(n \mapsto T_1(n) + T_2(n)\) is exponential-polynomial.
Let \(T_1, T_2 : \mathbb {N} \to \mathbb {N}\) both be exponential-polynomial, i.e. each is bounded by \(2^{K(n+1)^k}\) for all \(n\) and some constants \(K, k \in \mathbb {N}\). Then the product \(n \mapsto T_1(n) \cdot T_2(n)\) is exponential-polynomial.
Let \(T : \mathbb {N} \to \mathbb {N}\) be exponential-polynomial, i.e. \(T(n) \le 2^{K(n+1)^k}\) for all \(n\) and some constants \(K, k \in \mathbb {N}\). Then for all constants \(a, d \in \mathbb {N}\), the function \(n \mapsto T\bigl(a(n+1)^d\bigr)\) is also exponential-polynomial.
Let \(T : \mathbb {N} \to \mathbb {N}\) be exponential-polynomial, i.e. \(T(n) \le 2^{K(n+1)^k}\) for all \(n\) and some constants \(K, k \in \mathbb {N}\), and let \(L\) be a language over the binary alphabet in \(\mathrm{DTIME}(T)\), i.e. decided by some finite multi-tape Turing machine within \(c \cdot T(n)\) steps on inputs of length \(n\), for some constant \(c\). Then \(L \in \mathrm{EXP}\), that is, \(L \in \mathrm{DTIME}(2^{n^{c'}})\) for some constant \(c' \in \mathbb {N}\).