Realisability without cancellativity.
ProvedLogic.DPCompleteness.DPSpec.exists_backtrace_endingaether-cataloglogic
Realisability without cancellativity. Every DP value is attained by a backtrace.
theorem Logic.DPCompleteness.DPSpec.exists_backtrace_ending(D : DPSpec S W) :
∀ (n : ℕ) (s : S), ∃ f : ℕ → S, f n = s ∧ D.IsBacktrace n f := by sorry
Formalization Note Transplanted verbatim from the Aether Catalog source Logic/DPCompletenessConstrained.lean; the statement is byte-identical to the source declaration, elaborated with autoImplicit disabled in the platform environment.
Preamble
-- Thm stub generated from Logic/DPCompletenessConstrained.lean
import Mathlib
import Definitions.Def_Logic_DPCompleteness
import Definitions.Def_Logic_DPCompletenessConstrained
/-
# Completeness without cancellativity, and constrained dynamic programming
In `Logic.DPCompleteness` the notion `IsDPRun` was *semantic* (all prefix scores are optimal)
and the existence of runs was proved using cancellativity of the weight monoid. This file
removes that hypothesis by working with the *structural* (backtrace) notion of a run:
> `IsBacktrace D n f` : at each stage the DP recursion is realised on the nose,
> `val i (f i) + step i (f i) (f (i+1)) = val (i+1) (f (i+1))`.
The two notions turn out to be equivalent for **every** ordered weight monoid
(`isBacktrace_iff_isDPRun`), and completeness holds with no cancellativity assumption
(`dp_complete_general`). This is exactly what is needed to cover **constrained** dynamic
programming, where infeasible transitions carry the absorbing weight `⊥` of `WithBot W` — a
monoid that is emphatically *not* cancellative.
As an application we characterise infeasibility (`val_eq_bot_iff`) and instantiate the theory on
the classical maximum-weight independent set problem on a path.
-/
open Logic.DPCompleteness
open DPSpec
/-! ## Structural runs -/
variable {S W : Type*} [AddCommMonoid W] [Fintype S] [Nonempty S] [LinearOrder W] [AddLeftMono W]
omit [AddLeftMono W] inFormal statement
theorem Logic.DPCompleteness.DPSpec.exists_backtrace_ending(D : DPSpec S W) :
∀ (n : ℕ) (s : S), ∃ f : ℕ → S, f n = s ∧ D.IsBacktrace n f := by sorrySource