199 Complexity — Poly Time

199.1 Overview

This module introduces the class \(\mathrm{FP}\) of polynomial-time computable functions on bit strings that underlies every Karp reduction of [AB09, ch. 2]: a function \(f : \{ 0,1\} ^* \to \{ 0,1\} ^*\) is polynomial-time computable when some finite binary Turing machine computes it within \(C(n+1)^c\) steps on inputs of length \(n\). It fixes this polynomial normal form and proves the basic closure calculus used by the chapter’s reductions: the identity is polynomial-time computable, polynomial-time functions have polynomially bounded output length, and the class is closed under composition [AB09, Theorem 2.8].

199.2 Declarations

Definition 199.1 Polynomially bounded function

✓

A function \(p : \mathbb {N} \to \mathbb {N}\) is polynomially bounded if there are constants \(C, c \in \mathbb {N}\) such that \(p(n) \le C(n+1)^c\) for every \(n \in \mathbb {N}\). The function \(p\) itself need be neither monotone nor computable; only the majorant \(C(n+1)^c\) is.

Definition 199.2 Polynomial-time computable function

✓

A function \(f : \{ 0,1\} ^* \to \{ 0,1\} ^*\) on bit strings is polynomial-time computable if there exist a Turing machine \(M\) over the binary alphabet with finitely many states and constants \(C, c \in \mathbb {N}\) such that, on every input \(x\) of length \(n\), \(M\) halts within \(C(n+1)^c\) steps with \(f(x)\) written on its output tape. These functions form the class \(\mathrm{FP}\) implicit throughout [AB09, ch. 2].

Theorem 199.3 The identity is polynomial-time computable

✓

The identity function \(x \mapsto x\) on bit strings is polynomial-time computable: some finite binary Turing machine outputs \(x\) within \(C(n+1)^c\) steps on every input \(x\) of length \(n\), for some constants \(C, c \in \mathbb {N}\).

Theorem 199.4 Polynomial-time functions have polynomial output length

✓

Let \(f : \{ 0,1\} ^* \to \{ 0,1\} ^*\) be polynomial-time computable, i.e. some finite binary Turing machine computes \(f\) within \(C_0(n+1)^{c_0}\) steps on every input of length \(n\), for some constants \(C_0, c_0 \in \mathbb {N}\). Then there are constants \(C, c \in \mathbb {N}\) such that \(|f(x)| \le C(|x|+1)^c\) for every bit string \(x\).

Lemma 199.5 Polynomial bound for a composed time budget

✓

For all natural numbers \(a, C, c, C', c', n\),

\[ a\bigl(C(n+1)^c + C'\, (C(n+1)^c + 1)^{c'} + 1\bigr) \; \le \; a\bigl(C + C'(C+1)^{c'} + 1\bigr)\, (n+1)^{\max (c,\, c c')}. \]

Theorem 199.6 Polynomial-time functions are closed under composition

✓

Let \(f, g : \{ 0,1\} ^* \to \{ 0,1\} ^*\) be polynomial-time computable, where a function is polynomial-time computable if some finite binary Turing machine computes it within \(C(n+1)^c\) steps on every input of length \(n\), for some constants \(C, c \in \mathbb {N}\). Then the composition \(g \circ f\), mapping \(x\) to \(g(f(x))\), is also polynomial-time computable [AB09, proof of Theorem 2.8].