Branching between two circuit generators with an integer clock
ProvedF3SubsetSum.generator_branchThis is a machine-composition lemma used to assemble the circuit generator of Theorem 1.3.
Let be deterministic multi-stack Turing machines with Boolean input and output alphabets, and let . For write for the natural-number ceiling (so ) and define the clock
Then there are a machine and a constant such that for all and every output word :
- if and , started on , halts with output within steps, then , started on , halts with output within steps;
- if and , started on , halts with output within steps, then , started on , halts with output within steps.
So compares with , and in the first case writes the clock in unary and runs , in the second case runs directly. In the proof of Theorem 1.3, is the generator of Theorem 3.1 applied to the decoder of Theorem 1.7 (whose running time is at most for ), and is the exhaustive-search generator. The second branch pays no cost for the clock, which may be very large when .
Formalization Note Machines are Turing.TM2ComputableAux Bool Bool, run as in HMBinPacking.OutputsWithin; may depend on .
import Mathlib import Definitions.Def_HMBinPacking_OutputsWithin import Definitions.Def_F3SubsetSum_MachineCodes
namespace F3SubsetSum
/-- **Branching between two generators with an integer clock** (machine plumbing for the proof of
Theorem 1.3 of Kothari, Metger, O'Donnell, Shutty, Wu, arXiv:2609.40321v1, pp.22–23).
Given machines `G₁`, `G₂` and constants `K`, `d`, there are a machine `G` and a constant `C` such
that on input `1ⁿ 0 1ᵐ`:
* if `Kn ≤ m`, `G` computes the clock `T = ⌈m/n⌉^{d⌈n²/m⌉}` and then behaves like `G₁` on
`1ⁿ 0 1ᵐ 0 1ᵀ`: whenever `G₁` outputs `out` within `t` steps there, `G` outputs `out` within
`C(t + n + m + T + 1)^C` steps;
* if `m < Kn`, `G` behaves like `G₂` on the same input `1ⁿ 0 1ᵐ`, with time `C(t + n + m + 1)^C`.
**Formalization Note** Machines are `Turing.TM2ComputableAux Bool Bool`, run as in
`HMBinPacking.OutputsWithin`. The ceilings are natural-number ceilings, written
`⌈a/b⌉ = (a + b − 1)/b` (so the clock is defined for all `n`, `m`). `G` may depend on `G₁`, `G₂`,
`K`, `d`; the constant `C` absorbs the cost of computing the clock and of the comparison. -/
theorem generator_branch (G₁ G₂ : Turing.TM2ComputableAux Bool Bool) (K d : ℕ) :
∃ (G : Turing.TM2ComputableAux Bool Bool) (C : ℕ), ∀ (n m t : ℕ) (out : List Bool),
(K * n ≤ m →
HMBinPacking.OutputsWithin G₁
(unaryD n ++ unaryD m ++ unary (((m + n - 1) / n) ^ (d * ((n ^ 2 + m - 1) / m)))) out t →
HMBinPacking.OutputsWithin G (unaryD n ++ unary m) out
(C * (t + n + m + ((m + n - 1) / n) ^ (d * ((n ^ 2 + m - 1) / m)) + 1) ^ C)) ∧
(m < K * n →
HMBinPacking.OutputsWithin G₂ (unaryD n ++ unary m) out t →
HMBinPacking.OutputsWithin G (unaryD n ++ unary m) out (C * (t + n + m + 1) ^ C)) := by sorry
end F3SubsetSum