Proof of `Near-linear-time computation of Welzl orders`
What this proof establishes
no assumptions
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
Description
Near-linear Welzl-order algorithm. This proof assembles the construction's three independently proved contracts for the explicit source program.
Proof strategy
Take the sum of the three eventual resource thresholds. The runtime contract gives total halting on every tape. Every tape in the successful-final-state set yields a witness, and the output contract makes that output acceptable. Monotonicity of finite cardinality transfers the probability lower bound from successful tapes to accepted tapes.
Attribution
The contracts are three proved lemmas about the proof-local program witness. The assembled target is the registered claim of Lax195003; the graph result is Theorem 1.4 in the supplied arXiv v1 PDF.