OAI/Combinatorics/LowSpaceSubsetSum/Search/ExactFallback.lean

GitHub source file

7 declarations, 0 contain sorry, 0 declared as axioms

The exact small-input fallback as a depth-first subset search

The loop keeps the current target and a suffix of the input. It does not materialize the powerset. The work bound holds even when no branch accepts.

  1. def OAI.LowSpaceSubsetSum.ExactFallback.run line 15
  2. theorem OAI.LowSpaceSubsetSum.ExactFallback.run_work line 24
  3. theorem OAI.LowSpaceSubsetSum.ExactFallback.run_accepts line 39
  4. theorem OAI.LowSpaceSubsetSum.ExactFallback.weight_eq_list_sum line 66
  5. theorem OAI.LowSpaceSubsetSum.ExactFallback.run_correct line 76
  6. def OAI.LowSpaceSubsetSum.ExactFallback.decision line 97
  7. theorem OAI.LowSpaceSubsetSum.ExactFallback.decision_correct line 100