Theorem 1.1 — Warm-up protocol ( queries)
OpenSubquadCutReach.Faster.Supplement.theorem_1_1There is one uniform randomized zero-error outgoing-cut-oracle program deciding directed – reachability on every finite labelled oriented graph (no loops, no 2-cycles), with arbitrary terminals , including . Put and let be its stopping query count. Positive constants and a fixed logarithmic power, independent of graph, size and terminals, satisfy
For each fixed , constants , and a threshold , also independent of the input, satisfy for all . Every returning execution outputs the correct bit, termination is almost sure, and nontermination has infinite cost. The same program meets both cost bounds, and the graph is accessible only through outgoing-cut queries .
This is the warm-up headline of the paper: already subquadratic, through a shorter route than the mission's goal (Theorem 1.2, exponent ), which it is logically implied by. It is posed on its own and not derived from the goal.
Differences from the source:
- encoding: finite labelled oracle inputs and bounds in expectation and with high probability →
Fin n, finite rational-literal oracle programs, charged queries and the publishedSoftBoundswith outer uniform positive constants; reason: relabeling and the mission's operational cost semantics preserve the source input domain; nontermination has infinite cost
import Definitions.Def_SubquadCutReach_Faster_Tasks import Definitions.Def_SubquadCutReach_Faster_Supplement_Warmup set_option autoImplicit false
namespace SubquadCutReach.Faster.Supplement
open SubquadCutReach.Faster
/-- Theorem 1.1, p. 2 (PDF 4). One finite program, independent of size, graph and terminals;
zero error, both cost modes, query scale `n^(9/5)` up to polylogarithmic factors. -/
theorem theorem_1_1 :
∃ P : Program, Admissible P ∧ (∀ i : ReachCase, ReachCorrect P i) ∧
SoftBounds ReachCase ReachCase.n (reachCosts P) (fun i => warmScale i.n) := by sorry
end SubquadCutReach.Faster.Supplement