Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1 — deterministic near-linear single-source bicriteria RSP

Proved
NearLinearRSP.TwoResources.deterministic_bicriteria_rsp

by mikedeng1 · Nov 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

graph-theoryoperations-researchoptimizationp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1

There exist fixed finite deterministic real-RAM programs for preprocessing and witness retrieval, and one positive absolute constant KKK, uniformly for every finite directed graph with nnn vertices and mmm distinct ordered-pair edges, source sss, nonnegative real edge lengths ℓ\ellℓ and costs ccc, budget C≥0C\ge0C≥0, and accuracy 0<ε<10<\varepsilon<10<ε<1.

Preprocessing constructs a compact all-target data structure in at most

K max⁡(1,m)(1+log⁡max⁡(2,n))(1+log⁡(max⁡(2,n)W))ε9K\,\frac{\max(1,m)(1+\log\max(2,n))(1+\log(\max(2,n)W))}{\varepsilon^9}Kε9max(1,m)(1+logmax(2,n))(1+log(max(2,n)W))​

unit instructions. Here WWW is the ratio of the largest to smallest positive edge length, or one if all lengths are zero. There is exactly one suppressed log⁡n\log nlogn factor on nontrivial inputs.

For every target having an exactly CCC-feasible path, the stored distance dtd_tdt​ certifies a deterministically retrievable directed sss–ttt path PtP_tPt​, and

ℓ(Pt)≤dt≤(1+ε)OPT⁡C(t),c(Pt)≤(1+ε)C.\ell(P_t)\le d_t\le(1+\varepsilon)\operatorname{OPT}_C(t),\qquad c(P_t)\le(1+\varepsilon)C.ℓ(Pt​)≤dt​≤(1+ε)OPTC​(t),c(Pt​)≤(1+ε)C.

Every reported finite distance certifies a returned path with that upper length and relaxed budget, including targets that happen to have only relaxed-feasible paths. Every returned witness is valid. The guarantee is simultaneous for all targets and compares with the original budget. An infeasible target may have a relaxed-feasible answer; no exact infeasibility oracle is asserted.

The snapshot encodes the tables actually constructed by Section 4 and the two boundary shortest-path trees. Each target chooses its least accepted normalized guess, retains the same table for its path, and reports the extra inner length factor. With δ=ε/4\delta=\varepsilon/4δ=ε/4 and q=⌈512/δ2⌉q=\lceil512/\delta^2\rceilq=⌈512/δ2⌉, a witness query takes at most K(q+1)2(∣Pt∣+1)K(q+1)^2(|P_t|+1)K(q+1)2(∣Pt​∣+1) charged instructions, including path writing. An absent path has length zero in this query bound. Listing all target paths is separate from preprocessing.

Formalization Note Exact real +,−,×,÷+,-,\times,\div+,−,×,÷, comparisons <<< and ===, constants, copies and exp⁡\expexp each cost one instruction. Natural constants, copies, +++, truncated subtraction and comparisons, jumps and halt each cost one. Each indirect load, store or input-cell read costs one; operand-register access is included in its arithmetic instruction. No floor, real-to-integer conversion, logarithm, Poisson, heap or whole-DP instruction is available. Loops, coefficient generation and heap operations must be implemented and charged. Poisson probabilities are generated from exp by arithmetic, including the mean-zero case. The query receives the stored memory without copying it. Definitions specify computation and encodings; both successful execution and the time bounds are conclusions. The program witnesses and cost proofs remain to be supplied by solvers.

This formalizes the full headline deterministic bicriteria claim, including nonnegative inputs, compact all-target output and deterministic path retrieval, rather than only inner feasibility or nonconstructive path existence.

Differences from the source:

  • reading: infinite-precision real-RAM computation, with exact Poisson probabilities and generating functions → the explicitly listed exact field, comparison, exp, register, memory and control instructions, each costing one; reason: exact exp evaluation is required by the paper computation; no floor, real-to-integer conversion, log or algorithm oracle is provided
  • encoding: O-tilde(m log(nW)/epsilon^9), suppressing exactly one log n → one positive absolute coefficient outside all instances and epsilon multiplying max(1,m)(1+log(max(2,n)))(1+log(max(2,n)*W))/epsilon^9; reason: this is the stated asymptotic bound with totalized empty-edge and small-graph cases, without an instance-dependent coefficient
  • encoding: nonnegative resources with minor zero-weight bookkeeping → nonnegative real resources, explicit zero-length and zero-budget shortest-tree branches, W=1 when no length is positive, and self-loops ignored in computations; reason: all headline instances remain present; zero optima require zero output length and no division by a zero threshold
  • encoding: rescale epsilon by a constant, q=Theta(epsilon^-2), and normalized powers of 1+epsilon → delta=epsilon/4, q=ceil(512/delta^2), acceptance 1/4, both potential coefficients 1/8, and guesses a*(1+delta)^r through the first value at least n*b; reason: the explicit choices meet the tail and potential inequalities and preserve the exponent nine and both final factors 1+epsilon
  • encoding: compact single-source distances and deterministic witness retrieval from the retained tables → sparse memory encoding of the actual tables and boundary trees, a certified upper distance (1+delta)L from the selected table, and a fixed query program with charged output-sensitive cost (q+1)^2(path length+1); reason: implicit isolated targets avoid an uncharged linear-in-n initialization and explicit path writing is charged separately from preprocessing
  • encoding: approximation relative to an exactly budget-feasible optimum → the reported upper distance is at most (1+epsilon) times every exactly feasible comparator path length, with a returned path below that distance; reason: finite nonnegative graph optima are attained by cycle deletion; this formulation also handles zero optima and empty feasible sets without real-infimum defaults
  • encoding: deterministic choices left unspecified in the routines → first-minimum queue and pair ties, length on tick ties, a fixed edge-list input ABI and a fixed sparse output ABI; reason: these choices specify a single uniform computation and change no allowed instance or guarantee
Preamble
import Definitions.Def_NearLinearRSP_TwoResources_RAM

set_option autoImplicit false
Formal statement
namespace NearLinearRSP.TwoResources

theorem deterministic_bicriteria_rsp :
    ∃ preprocessing retrieval : Program, ∃ K : ℝ, 0 < K ∧
      ∀ (I : Instance) (ε : ℝ), 0 < ε → ε < 1 →
        ∃ (steps : ℕ) (snapshot : RAMState),
          Execution preprocessing (encodeInput I ε) initialState snapshot steps ∧
          (steps : ℝ) ≤ K * preprocessingScale I ε ∧ EncodesOutput I ε snapshot ∧
          ∀ t : ℕ, t < I.graph.n →
            readDistance snapshot t = answerDistance I ε t ∧
            (∃ (querySteps : ℕ) (out : RAMState),
              Execution retrieval (encodeInput I ε) (queryStart snapshot t) out querySteps ∧
              queryPath out = answerPath I ε t ∧
              (querySteps : ℝ) ≤ K * retrievalScale ε (answerPath I ε t)) ∧
            (∀ d : ℝ, readDistance snapshot t = some d →
              ∃ P : List ℕ, answerPath I ε t = some P ∧
                IsPath I.graph I.source t P ∧ pathWeight I.length P ≤ d ∧
                pathWeight I.cost P ≤ (1 + ε) * I.budget ∧
                ∀ R : List ℕ, Feasible I t R → d ≤ (1 + ε) * pathWeight I.length R) ∧
            ((∃ R : List ℕ, Feasible I t R) → (readDistance snapshot t).isSome = true) ∧
            (∀ P : List ℕ, answerPath I ε t = some P →
              IsPath I.graph I.source t P ∧ pathWeight I.cost P ≤ (1 + ε) * I.budget) := by sorry

end NearLinearRSP.TwoResources
Source
Vikrant Ashvinkumar, STOC 2027 submission #289 (October 2026), p.3, Theorem 1 and following paragraph; Definition 1.1 p.2; proof pp.6–12 and 14
Human review
  • Endorsed by Shuze Chen · Nov 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 8, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me