192 Complexity — Counter Prog Poly Time
192.1 Overview
This module shows that a counter program (a goto program over finitely many unary natural-number registers that reads its input once and prints bits) which halts within polynomially many abstract steps computes a polynomial-time computable function: its compiled multi-tape Turing machine simulates \(t\) abstract steps within \(t(2t+3)\) machine steps. This is how the emitters of [AB09, Remark 6.7] are shown to run in polynomial time.
192.2 Declarations
Let \(P\) be a counter program over \(R\) natural-number registers with a finite set of labels \(\Lambda \), i.e. an assignment to each label of one instruction (halt, jump, print a bit, increment a register, decrement a register saturating at \(0\), branch on a register being zero, print the value \(v\) of a register as \(1^v\), or read and consume the next input bit, branching on end-of-input, \(0\) or \(1\)). Fix a start label \(\ell _0 \in \Lambda \), a function \(f : \{ 0,1\} ^* \to \{ 0,1\} ^*\) and constants \(C, c \in \mathbb {N}\), and suppose that for every input \(x \in \{ 0,1\} ^*\) there is some \(t \le C(|x|+1)^c\) such that running \(P\) on \(x\) for \(t\) steps from the initial state (label \(\ell _0\), all registers \(0\), no input read, empty output) reaches a halted state whose output is \(f(x)\). Then \(f\) is polynomial-time computable: some finite binary-alphabet Turing machine computes \(f\) within \(C'(n+1)^{c'}\) steps on every input of length \(n\), for some constants \(C', c' \in \mathbb {N}\).
Let \(P\) be a counter program over \(R\) natural-number registers with a finite set of labels \(\Lambda \) (each label carrying one instruction: halt, jump, print a bit, increment, saturating decrement, zero-test branch, print a register’s value \(v\) as \(1^v\), or read and consume the next input bit), let \(\ell _0 \in \Lambda \), let \(f : \{ 0,1\} ^* \to \{ 0,1\} ^*\) and let \(C, c \in \mathbb {N}\). Suppose that for every input \(x \in \{ 0,1\} ^*\) there are register values \(\rho : \{ 0,\dots ,R-1\} \to \mathbb {N}\) and a position \(p \in \mathbb {N}\) such that, for every previously printed output \(o\), running \(P\) on \(x\) from label \(\ell _0\) with all registers \(0\), no input read and output \(o\) reaches, within at most \(C(|x|+1)^c\) steps, the halted state with registers \(\rho \), \(p\) input bits read and output \(o\) followed by \(f(x)\). Then \(f\) is polynomial-time computable: some finite binary-alphabet Turing machine computes \(f\) within \(C'(n+1)^{c'}\) steps on every input of length \(n\), for some constants \(C', c' \in \mathbb {N}\).