Removing zeros and reversing preserves PARTITION
ProvedProjSchedTW.Complexity.partitionYes_filter_reversecombinatoricscomplexity-theory
For any finite list of natural numbers, deleting all zero entries and reversing the remaining list preserves whether its indexed entries admit a partition into two equal sums. Zero entries contribute nothing, and reversal only relabels the indices. This is the preprocessing invariant needed by the binary encoding reduction to the two-agent scheduling problem.
Preamble
import Mathlib import Definitions.Def_ProjSchedTW_Complexity_Encoding open ProjSchedTW.Complexity
Formal statement
theorem ProjSchedTW.Complexity.partitionYes_filter_reverse (xs : List ℕ) :
PartitionYes xs ↔ PartitionYes ((xs.filter (fun a => a ≠ 0)).reverse) := by sorrySource
Supporting preprocessing lemma for the ProjSchedTW.Complexity PARTITION language and the two-agent scheduling encoding reduction.