OAI/Combinatorics/LowSpaceSubsetSum/Search/MainGuard.lean

GitHub source file

3 declarations, 0 contain sorry, 0 declared as axioms

An integer main-branch guard and the polynomial-bit promise

The guard uses the binary ceiling logarithm. It implies the manuscript's real logarithmic guard and eventually passes for every fixed polynomial bound on input bit length. Its stricter rounding only changes the fallback on a finite initial range for each polynomial-bit promise.

  1. def OAI.LowSpaceSubsetSum.mainGuard line 17
  2. theorem OAI.LowSpaceSubsetSum.mainGuard_log line 19
  3. theorem OAI.LowSpaceSubsetSum.eventually_mainGuard line 34