AFTD Auto-Formalizing Theoretical Domains

is_valid_policy_stop

theoremverified

For every Pandora's problem instance with deadlines inst : PandoraDeadlineInstance, the policy AdaptivePolicy.stop satisfies IsValidPolicy inst AdaptivePolicy.stop.

Statement

theorem is_valid_policy_stop (inst : PandoraDeadlineInstance) :
    IsValidPolicy inst AdaptivePolicy.stop
Source
step towards op184_partially_adaptive_beyond_half
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • IsValidPolicyA policy is valid for a Pandora's problem instance with deadlines if it respects opening deadlines and never opens any box more than once.
  • IsValidPolicyAuxA policy execution is valid if it never re-opens an already opened box, respects the deadline of each opened box, and remains valid on all…
  • PandoraDeadlineInstanceAn instance of Pandora's problem with deadlines consisting of n boxes, each with a non-negative opening cost, a positive integer deadline,…
  • AdaptivePolicyA fully adaptive search policy for Pandora's problem with n boxes, represented as a decision tree that at each step either stops or opens…
Used by 2
  • opt_dus_nonnegFor any Pandora deadline instance inst, 0 ≤ optDUS inst.
  • dus_approx_of_pos_optIf a constant factor approximation ratio c is achieved by partially adaptive policies on all instances with optDUS > 0, then it is…

Lean source view module on GitHub

/-- The stop policy AdaptivePolicy.stop is always valid for any Pandora deadline instance. -/
theorem is_valid_policy_stop (inst : PandoraDeadlineInstance) :
    IsValidPolicy inst AdaptivePolicy.stop := by
  unfold IsValidPolicy
  rw [IsValidPolicyAux.eq_1]
  trivial
See it in the graphDiscuss this resultChallenge it