OAI/Combinatorics/LowSpaceSubsetSum/Word/WordRejection.lean

GitHub source file

7 declarations, 0 contain sorry, 0 declared as axioms

A fair-word implementation of the measured bounded rejection loop

Only the polynomial-size candidate tuple is drawn and retained. The same measured evaluator then supplies output, read count, and test-work count.

  1. def OAI.LowSpaceSubsetSum.WordRejection.run line 16
  2. theorem OAI.LowSpaceSubsetSum.WordRejection.bounded line 21
  3. theorem OAI.LowSpaceSubsetSum.WordRejection.probability line 28
  4. def OAI.LowSpaceSubsetSum.WordRejection.sample line 39
  5. theorem OAI.LowSpaceSubsetSum.WordRejection.sample_bounded line 44
  6. theorem OAI.LowSpaceSubsetSum.WordRejection.sample_probability line 51
  7. theorem OAI.LowSpaceSubsetSum.WordRejection.sample_expectation line 60