OAI/Combinatorics/LowSpaceSubsetSum/Streams/SortedFind.lean

GitHub source file

4 declarations, 0 contain sorry, 0 declared as axioms

Linear exact-key search for the separator's terminal arrays

At a terminal separator node every left/right pair is disjoint. One equal weight key therefore suffices. This loop stops at the first equal key and never enumerates its Cartesian tie group. The finite reader law supplies exactness, and the ledger charges at most two reads per control step.

  1. def OAI.LowSpaceSubsetSum.SortedFind.runAcc line 19
  2. theorem OAI.LowSpaceSubsetSum.SortedFind.queries_le line 33
  3. theorem OAI.LowSpaceSubsetSum.SortedFind.sound line 54
  4. theorem OAI.LowSpaceSubsetSum.SortedFind.correct line 86