bug: 5 unsound reductions — reduce_to() constructions are mathematically incorrect

[zazabap]

Summary

Five reductions have unsound reduce_to() constructions — target feasibility does not imply source feasibility. Confirmed by brute-force exhaustive search on NO instances.

Affected Rules

Rule	PR	Root Cause	NO-instance evidence
HamiltonianPath → ConsecutiveOnesSubmatrix	#779	C1P on incidence matrix is necessary but not sufficient for HP	6-vertex graph: 30 C1P solutions, only 10 are valid paths
Partition → ShortestWeightConstrainedPath	#779	Weight bound S/2 + n is an inequality — non-partition paths satisfy it	[1,2,6] (odd sum): target has feasible path. [1,2,3,10]: same.
ThreePartition → FlowShopScheduling	#972	Separator [0,L,0] only blocks machine 1. ALL permutations meet deadline.	[4,4,4,6,6,6], B=15: 2520 feasible schedules (should be 0)
ThreePartition → SeqMinWeightTardiness	#972	Element deadlines = horizon, so elements are never tardy	[4,4,4,6,6,6], B=15: 2520 zero-tardiness schedules (should be 0)
ThreePartition → JobShopScheduling	#972	Separator only constrains machine 0. Threshold = machine-0 total.	Optimal makespan always achievable regardless of partition

Verified Sound (38 rules)

All other rules from PRs #777, #779, #804, #972 were tested with NO instances and/or code-reviewed against textbook constructions. Notable:

• ThreePartition → ResourceConstrainedScheduling: SOUND (structural constraint enforces exactly 3 per slot)
• ThreePartition → SequencingWithReleaseTimesAndDeadlines: SOUND (fillers rigidly pinned with release=deadline-1)
• All HC→X (6 rules): SOUND (budget/penalty arguments verified)
• All KSat→X, Partition→{BinPacking,SubsetSum,MultiprocessorScheduling,SequencingWithinIntervals}: SOUND

Why Unit Tests Pass

Closed-loop tests only verify the forward direction or check "at least some brute-force witnesses extract correctly." They never test NO instances (infeasible source → target should be infeasible).

Discovery Method

Systematic CLI round-trip testing found 4 rules where ILP witnesses extracted to invalid source configs. Deeper investigation revealed the reductions themselves are unsound. A 5th (Partition→SWCP) was found by extending NO-instance testing to all 39 surviving rules.

Fix Options

1. Fix the reductions — redesign reduce_to() with correct constructions from literature
2. Remove the 5 unsound reductions — delete rule files, tests, paper entries, registry entries
3. Replace with correct multi-hop chains — keep problem models, remove incorrect direct edges

Supersedes

#1000, #1001, #1002, #1003, #1004 (all closed)