Theorem: HMem.Trace.CostedProgram.splitTimeCost
Proof state before:
case h₁.h₁
α : Type u_1
inst✝⁵ : Complexity.Coding α Memory
β : Type u_2
inst✝⁴ : Complexity.Encoding β Memory
f : α → β
tp : TracedProgram
γ δ : Type
inst✝³ : Complexity.Coding γ Memory
inst✝² : Complexity.Encoding δ Memory
fs : γ → δ
cs : Complexity.CostFunction γ ℕ
inst✝¹ : Complexity.Computable Encoding.Model fs
inst✝ : Complexity Encoding.Model fs cs
size : α → ℕ
fm : α → Option Memory
fcp : CostedProgram
hf : Program.sound (TracedProgram.toProgram (toTracedProgram fcp)) f size
dst✝ src✝ : Source
next✝ : CostedProgram
h : TracedProgram.sound' f size (toTracedProgram (recurse dst✝ src✝ next✝)) fm
x✝¹ : α
x✝ : Memory
hm : x✝ ∈ fm x✝¹
⊢ (subroutineTimeCost
              (_ :
                TracedProgram.sound' f size (toTracedProgram next✝)
                  ((flip Option.bind fun m =>
                      Option.map (Memory.setms m dst✝ ∘ Complexity.encode ∘ f)
                        (Complexity.decode α (Memory.getms m src✝))) ∘
                    fm)) +
            recurseTimeCost hf
              (_ :
                TracedProgram.sound' f size (toTracedProgram next✝)
                  ((flip Option.bind fun m =>
                      Option.map (Memory.setms m dst✝ ∘ Complexity.encode ∘ f)
                        (Complexity.decode α (Memory.getms m src✝))) ∘
                    fm)) +
          localTimeCost
            (_ :
              TracedProgram.sound' f size (toTracedProgram next✝)
                ((flip Option.bind fun m =>
                    Option.map (Memory.setms m dst✝ ∘ Complexity.encode ∘ f)
                      (Complexity.decode α (Memory.getms m src✝))) ∘
                  fm)))
        x✝¹ +
      Stack.timeCost
        (Stack.execution
          {
            state :=
              Complexity.encode
                (Option.get (Complexity.decode α (Memory.getms x✝ src✝))
                  (_ : Option.isSome (Complexity.decode α (Memory.getms x✝ src✝)) = true)),
            current := toProgram fcp, function := toProgram fcp }
          [])
        (_ :
          Program.haltsOn (TracedProgram.toProgram (toTracedProgram fcp))
            (Complexity.encode
              (Option.get (Complexity.decode α (Memory.getms x✝ src✝))
                (_ : Option.isSome (Complexity.decode α (Memory.getms x✝ src✝)) = true)))) =
    ?h₁.b

case h₁.h₂
α : Type u_1
inst✝⁵ : Complexity.Coding α Memory
β : Type u_2
inst✝⁴ : Complexity.Encoding β Memory
f : α → β
tp : TracedProgram
γ δ : Type
inst✝³ : Complexity.Coding γ Memory
inst✝² : Complexity.Encoding δ Memory
fs : γ → δ
cs : Complexity.CostFunction γ ℕ
inst✝¹ : Complexity.Computable Encoding.Model fs
inst✝ : Complexity Encoding.Model fs cs
size : α → ℕ
fm : α → Option Memory
fcp : CostedProgram
hf : Program.sound (TracedProgram.toProgram (toTracedProgram fcp)) f size
dst✝ src✝ : Source
next✝ : CostedProgram
h : TracedProgram.sound' f size (toTracedProgram (recurse dst✝ src✝ next✝)) fm
x✝¹ : α
x✝ : Memory
hm : x✝ ∈ fm x✝¹
⊢ ?h₁.b = ?b

case h₁.b
α : Type u_1
inst✝⁵ : Complexity.Coding α Memory
β : Type u_2
inst✝⁴ : Complexity.Encoding β Memory
f : α → β
tp : TracedProgram
γ δ : Type
inst✝³ : Complexity.Coding γ Memory
inst✝² : Complexity.Encoding δ Memory
fs : γ → δ
cs : Complexity.CostFunction γ ℕ
inst✝¹ : Complexity.Computable Encoding.Model fs
inst✝ : Complexity Encoding.Model fs cs
size : α → ℕ
fm : α → Option Memory
fcp : CostedProgram
hf : Program.sound (TracedProgram.toProgram (toTracedProgram fcp)) f size
dst✝ src✝ : Source
next✝ : CostedProgram
h : TracedProgram.sound' f size (toTracedProgram (recurse dst✝ src✝ next✝)) fm
x✝¹ : α
x✝ : Memory
hm : x✝ ∈ fm x✝¹
⊢ ℕ

case h₂
α : Type u_1
inst✝⁵ : Complexity.Coding α Memory
β : Type u_2
inst✝⁴ : Complexity.Encoding β Memory
f : α → β
tp : TracedProgram
γ δ : Type
inst✝³ : Complexity.Coding γ Memory
inst✝² : Complexity.Encoding δ Memory
fs : γ → δ
cs : Complexity.CostFunction γ ℕ
inst✝¹ : Complexity.Computable Encoding.Model fs
inst✝ : Complexity Encoding.Model fs cs
size : α → ℕ
fm : α → Option Memory
fcp : CostedProgram
hf : Program.sound (TracedProgram.toProgram (toTracedProgram fcp)) f size
dst✝ src✝ : Source
next✝ : CostedProgram
h : TracedProgram.sound' f size (toTracedProgram (recurse dst✝ src✝ next✝)) fm
x✝¹ : α
x✝ : Memory
hm : x✝ ∈ fm x✝¹
⊢ ?b ≤
    (subroutineTimeCost h + recurseTimeCost hf h) x✝¹ +
      localTimeCost
        (_ :
          TracedProgram.sound' f size (toTracedProgram next✝)
            ((flip Option.bind fun m =>
                Option.map (Memory.setms m dst✝ ∘ Complexity.encode ∘ f) (Complexity.decode α (Memory.getms m src✝))) ∘
              fm))
        x✝¹

case b
α : Type u_1
inst✝⁵ : Complexity.Coding α Memory
β : Type u_2
inst✝⁴ : Complexity.Encoding β Memory
f : α → β
tp : TracedProgram
γ δ : Type
inst✝³ : Complexity.Coding γ Memory
inst✝² : Complexity.Encoding δ Memory
fs : γ → δ
cs : Complexity.CostFunction γ ℕ
inst✝¹ : Complexity.Computable Encoding.Model fs
inst✝ : Complexity Encoding.Model fs cs
size : α → ℕ
fm : α → Option Memory
fcp : CostedProgram
hf : Program.sound (TracedProgram.toProgram (toTracedProgram fcp)) f size
dst✝ src✝ : Source
next✝ : CostedProgram
h : TracedProgram.sound' f size (toTracedProgram (recurse dst✝ src✝ next✝)) fm
x✝¹ : α
x✝ : Memory
hm : x✝ ∈ fm x✝¹
⊢ ℕ
Tactic:
apply add_comm
Proof state after:
case h₁.h₂
α : Type u_1
inst✝⁵ : Complexity.Coding α Memory
β : Type u_2
inst✝⁴ : Complexity.Encoding β Memory
f : α → β
tp : TracedProgram
γ δ : Type
inst✝³ : Complexity.Coding γ Memory
inst✝² : Complexity.Encoding δ Memory
fs : γ → δ
cs : Complexity.CostFunction γ ℕ
inst✝¹ : Complexity.Computable Encoding.Model fs
inst✝ : Complexity Encoding.Model fs cs
size : α → ℕ
fm : α → Option Memory
fcp : CostedProgram
hf : Program.sound (TracedProgram.toProgram (toTracedProgram fcp)) f size
dst✝ src✝ : Source
next✝ : CostedProgram
h : TracedProgram.sound' f size (toTracedProgram (recurse dst✝ src✝ next✝)) fm
x✝¹ : α
x✝ : Memory
hm : x✝ ∈ fm x✝¹
⊢ Stack.timeCost
        (Stack.execution
          {
            state :=
              Complexity.encode
                (Option.get (Complexity.decode α (Memory.getms x✝ src✝))
                  (_ : Option.isSome (Complexity.decode α (Memory.getms x✝ src✝)) = true)),
            current := toProgram fcp, function := toProgram fcp }
          [])
        (_ :
          Program.haltsOn (TracedProgram.toProgram (toTracedProgram fcp))
            (Complexity.encode
              (Option.get (Complexity.decode α (Memory.getms x✝ src✝))
                (_ : Option.isSome (Complexity.decode α (Memory.getms x✝ src✝)) = true)))) +
      (subroutineTimeCost
              (_ :
                TracedProgram.sound' f size (toTracedProgram next✝)
                  ((flip Option.bind fun m =>
                      Option.map (Memory.setms m dst✝ ∘ Complexity.encode ∘ f)
                        (Complexity.decode α (Memory.getms m src✝))) ∘
                    fm)) +
            recurseTimeCost hf
              (_ :
                TracedProgram.sound' f size (toTracedProgram next✝)
                  ((flip Option.bind fun m =>
                      Option.map (Memory.setms m dst✝ ∘ Complexity.encode ∘ f)
                        (Complexity.decode α (Memory.getms m src✝))) ∘
                    fm)) +
          localTimeCost
            (_ :
              TracedProgram.sound' f size (toTracedProgram next✝)
                ((flip Option.bind fun m =>
                    Option.map (Memory.setms m dst✝ ∘ Complexity.encode ∘ f)
                      (Complexity.decode α (Memory.getms m src✝))) ∘
                  fm)))
        x✝¹ =
    ?b

case h₂
α : Type u_1
inst✝⁵ : Complexity.Coding α Memory
β : Type u_2
inst✝⁴ : Complexity.Encoding β Memory
f : α → β
tp : TracedProgram
γ δ : Type
inst✝³ : Complexity.Coding γ Memory
inst✝² : Complexity.Encoding δ Memory
fs : γ → δ
cs : Complexity.CostFunction γ ℕ
inst✝¹ : Complexity.Computable Encoding.Model fs
inst✝ : Complexity Encoding.Model fs cs
size : α → ℕ
fm : α → Option Memory
fcp : CostedProgram
hf : Program.sound (TracedProgram.toProgram (toTracedProgram fcp)) f size
dst✝ src✝ : Source
next✝ : CostedProgram
h : TracedProgram.sound' f size (toTracedProgram (recurse dst✝ src✝ next✝)) fm
x✝¹ : α
x✝ : Memory
hm : x✝ ∈ fm x✝¹
⊢ ?b ≤
    (subroutineTimeCost h + recurseTimeCost hf h) x✝¹ +
      localTimeCost
        (_ :
          TracedProgram.sound' f size (toTracedProgram next✝)
            ((flip Option.bind fun m =>
                Option.map (Memory.setms m dst✝ ∘ Complexity.encode ∘ f) (Complexity.decode α (Memory.getms m src✝))) ∘
              fm))
        x✝¹

case b
α : Type u_1
inst✝⁵ : Complexity.Coding α Memory
β : Type u_2
inst✝⁴ : Complexity.Encoding β Memory
f : α → β
tp : TracedProgram
γ δ : Type
inst✝³ : Complexity.Coding γ Memory
inst✝² : Complexity.Encoding δ Memory
fs : γ → δ
cs : Complexity.CostFunction γ ℕ
inst✝¹ : Complexity.Computable Encoding.Model fs
inst✝ : Complexity Encoding.Model fs cs
size : α → ℕ
fm : α → Option Memory
fcp : CostedProgram
hf : Program.sound (TracedProgram.toProgram (toTracedProgram fcp)) f size
dst✝ src✝ : Source
next✝ : CostedProgram
h : TracedProgram.sound' f size (toTracedProgram (recurse dst✝ src✝ next✝)) fm
x✝¹ : α
x✝ : Memory
hm : x✝ ∈ fm x✝¹
⊢ ℕ