§3, TEST(V), first case, p. 38 — if TEST(V) = NO, a T-path of length < V(1 + ε) exists
ProvedHassinRSP.Rounding.test_no_specConsider an instance of the restricted shortest path problem (vertices , , edges with , positive integer lengths and transition times ), a time budget , and a real . Hassin's test is specified at the top of §3: "This test has the following properties: If it outputs a positive answer then definitely OPT . If it outputs a negative answer, then all we know is that OPT ." This statement is the negative half.
If TEST(V) outputs NO — that is, for some integer there is a – path using only edges with , of transition time at most and of rounded length — then there is a -path with
In particular OPT . The paper obtains the path's length bound . This is what allows the Rounding Algorithm to lower its upper bound to after a NO answer.
Formalization Note. OPT is not a Lean term (it is when no -path exists); "OPT " is expressed by exhibiting a -path. The hypotheses and are not needed and are omitted: for no edge survives the pruning, so TEST(V) never answers NO.
import Mathlib import Definitions.Def_HassinRSP_Rounding_Setting
namespace HassinRSP.Rounding
theorem test_no_spec (I : Instance) (hI : I.WellFormed) (T : ℕ) (ε : ℝ) (hε0 : 0 < ε)
(V : ℝ) :
testNo I T ε V → ∃ q, IsTPath I T q ∧ (pathLen I q : ℝ) < V * (1 + ε) := by sorry
end HassinRSP.Rounding
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.