Variable Bound: st Search D
ProvedVariableBound.stSearchDalgorithmsanthropic-eth-16a5ce4complexity-theory
Step 2, the algorithm as a program: under the hypotheses listed at StSearchD, the list that
searchD finds has the bounds of Step 2 (StructD) and X = 0.
Preamble
/- Copyright (c) 2026 Anthropic, PBC. All rights reserved. Released under Apache 2.0; SPDX-License-Identifier: Apache-2.0. Source and original notices: https://github.com/anthropics/formal-math/blob/16a5ce41304fcdaea4e0be7c132e1c361dc26da5/eth/NOTICE -/ import Definitions.Def_VariableBound_Search_Defs import Definitions.Def_VariableBound_StepChoice import Mathlib.Algebra.BigOperators.Fin import Mathlib.Algebra.BigOperators.Ring.Finset import Mathlib.Algebra.Order.Field.Basic import Mathlib.Tactic.FieldSimp import Mathlib.Tactic.Linarith import Mathlib.Tactic.NormNum import Mathlib.Tactic.Positivity import Mathlib.Tactic.Ring import Definitions.Def_VariableBound_Search_Correct set_option autoImplicit false section section open VariableBound open Groundwork PaddedDescent.F AppVariables Finset
Formal statement
theorem VariableBound.stSearchD : StSearchD := by sorry
Source