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…
- opt_dus_nonnegFor any Pandora deadline instance
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