Polynomial time verifier and reduction interface

A head visits at most T new cells in T transitions. Thus an output word occupies at most its initially occupied input extent plus T plus one cells: a polynomial time bound gives a polynomial output-length bound when input and output share a tape, and at most T plus one on an initially blank output tape. For composition of reductions with time/length bounds $C(n+1{)}^a$ and $D(n+1{)}^b$, the first output has length at most $n+C(n+1{)}^a+1$. Retain that result on work tapes and run the second fixed machine on it. The two fixed programs can be joined on finitely many tapes, with linear copying/preparation time. Their combined time is bounded by a constant multiple of $C(n+1{)}^a+D(n+C(n+1{)}^a+2{)}^b+n+1$, a polynomial. The membership iff composes, proving transitivity.

If fixed-length certificates are wanted, let $P=p(\mathrm{\mid }x\mathrm{\mid })$. Encode a witness w of length $\mathrm{\ell }\le P$ by the length field $1^{\mathrm{\ell }}{0}^{P+1-\mathrm{\ell }}$ followed by $w{0}^{P-\mathrm{\ell }}$, a word of length $2P+1$. The verifier rejects certificates whose total length is not $2P+1$, then checks the field consists of at most P initial ones followed by zeros, then checks the last $P-\mathrm{\ell }$ payload bits are zero, and applies R to the first $\mathrm{\ell }$ payload bits. Every guarded witness has this encoding, and every accepted encoding decodes one guarded witness. Scanning and evaluating p in binary and writing at most polynomially many cells are polynomial operations for the fixed polynomial p (successive addition/multiplication of its fixed number of binary factors suffices). The case P=0 has certificate 0 and decoded empty witness. This optional padding therefore preserves the language and polynomial bounds.