The deterministic time class
DefinitionFRouting_Supplement_InDTIMEf-routingp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-position-verification
For , a promise problem on binary strings is in if a single deterministic machine , on every instance , halts within steps with output if and if . A language is the promise problem .
This is the class in the conclusion of Theorem 1.5.
Formalization Note Machines are the base mission's string machines (Mathlib multi-stack Turing machines over ).
Definition code
import Definitions.Def_FRouting_StrMachine
import Definitions.Def_FRouting_languageOf
set_option autoImplicit false
namespace FRouting.Supplement
open QAlgorithms.Complexity
/-- **Membership in `DTIME(B)`.** Renard, *Computational Bounds for f-Routing*, arXiv:2609.40278 (held
copy, sha256 4a327f29…), Theorem 1.5, p.5, uses the deterministic time class without defining it. A
promise problem is in `DTIME(B)` when one deterministic machine `M`, on every instance `w`, halts within
the budget of `B |w|` steps, printing `[true]` on Yes instances and `[false]` on No instances.
**Formalization Note** The machine is the published `FRouting.StrMachine` (a Mathlib `FinTM2`), the same
model as the base mission's verifiers. `budget B` is `max 1 B`, which differs from `B` only where
`B = 0`. -/
def InDTIME (P : PromiseProblem) (B : ℕ → ℕ) : Prop :=
∃ M : StrMachine,
(∀ w ∈ P.Yes, PrintsInTime M w [true] (budget B w.length)) ∧
(∀ w ∈ P.No, PrintsInTime M w [false] (budget B w.length))
end FRouting.Supplement
Source
Renard, Computational Bounds for f-Routing, arXiv:2609.40278 (held copy, sha256 4a327f29…), Theorem 1.5, p.5