Time-constructible functions
DefinitionTimeSpaceMA_Supplement_TimeConstructiblecomplexity-theorymerlin-arthurp2o-gran-per-chapterp2o-plan-paperp2o-v1time-space-complexity
A function is time-constructible if one fixed machine, on the unary input , writes a unary word of length and halts in time.
This is the standard clock-machine form of the hypothesis in Theorem 4.1. The clock may have any fixed finite number of sequential work tapes; time constructibility constrains the bound , not the one-tape language decider.
Formalization Note The clock is a published TimeSpaceMA.RATM. On one output tape, cells carry a nonblank marker and cell is blank; the machine is halted after at most steps for one uniform .
Definition code
import Definitions.Def_TimeSpaceMA_RATM
set_option autoImplicit false
namespace TimeSpaceMA
namespace Supplement
/-- A function `t : ℕ → ℕ` is time-constructible (Williams–Xi, *Short Non-Interactive
Proofs for Time-Space Computations*, STOC 2027 submission, manuscript sha256 184c2f95…,
Theorem 4.1, p.23) when one fixed machine, on unary input of length `n`, writes a unary word of
length `t n` and halts in `O(t n)` time.
**Formalization Note** The paper uses the standard complexity-theoretic term without defining a
machine. Here the clock is a published `TimeSpaceMA.RATM`; its work-tape count is unrestricted,
because time constructibility is a property of the bound rather than the one-tape decider. The
unary input is `true^n`. On one output tape, cells `0,…,t(n)-1` contain a nonblank marker and cell
`t(n)` is blank. The uniform time cap is `C·t(n)+C`, with `C>0`. -/
def TimeConstructible (t : ℕ → ℕ) : Prop :=
∃ (M : RATM) (out : Fin M.k) (mark : M.Γ) (C : ℕ), mark ≠ M.blank ∧ 0 < C ∧
∀ n : ℕ,
let c := M.run (List.replicate n true) (C * t n + C)
(c.state = M.qaccept ∨ c.state = M.qreject) ∧
(∀ j < t n, c.tape out (j : ℤ) = mark) ∧ c.tape out (t n : ℤ) = M.blank
end Supplement
end TimeSpaceMA
Source
Williams, Xi, Short Non-Interactive Proofs for Time-Space Computations, STOC 2027 submission (manuscript sha256 184c2f95…), Theorem 4.1, p.23 (standard term used without a separate definition)