Context
PRs #999 and #1010 batch-implemented 28 reduction rules from the reinspected derivation document (reduction_derivations_low_tier_reinspected.typ). This issue tracks the 57 remaining rules that were skipped, organized by failure mode, for future reference.
Actionable (High/Medium confidence)
| Source → Target |
Issue |
Notes |
| SchedulingToMinimizeWeightedCompletionTime → ILP |
#783 |
Direct ILP formulation — high confidence, likely just needs implementation |
| 3SAT → MonochromaticTriangle |
#884 |
Medium-ish — clause-gadget converse lemma unresolved |
Low confidence — by failure mode
Explicit counterexamples or refutations (6)
These were tested and found unsound:
| Source → Target |
Issue |
| MinimumMaximalMatching → MaximumAchromaticNumber |
#846 |
| Graph3Colorability → PartitionIntoForests |
#843 |
| MinimumMaximalMatching → MinimumMatrixDomination |
#847 |
| ExactCoverBy3Sets → AcyclicPartition |
#822 |
| ExactCoverBy3Sets → BoundedDiameterSpanningTree |
#913 |
| 3SAT → DisjointConnectingPaths |
#370 |
Type mismatch (optimization vs feasibility) (4)
The source and target problems have incompatible value types:
| Source → Target |
Issue |
Detail |
| VertexCover → HamiltonianCircuit |
#198 |
Min optimization → feasibility |
| VertexCover → HamiltonianPath |
#892 |
Min optimization → feasibility |
| MaxCut → OptimalLinearArrangement |
#890 |
Exact transformed bound missing |
| OptimalLinearArrangement → RootedTreeArrangement |
#888 |
Naive identity map fails; Gavril gadget unavailable |
Not a Karp reduction (1)
| Source → Target |
Issue |
Detail |
| Partition → KthLargestMTuple |
#395 |
Only a Turing/counting reduction |
One-way embedding only (3)
Forward reduction exists but solution extraction is impossible:
| Source → Target |
Issue |
Detail |
| PartitionIntoCliques → MinimumCoveringByCliques |
#889 |
One-way NP-hardness map only |
| SubsetSum → IntegerKnapsack |
#521 |
Unrestricted knapsack solutions don't decode back |
| MinimumVertexCover → MinimumMaximalMatching |
#893 |
Factor-2 correspondence, not exact many-one |
Missing gadget data or unresolved converse (4)
| Source → Target |
Issue |
| 3SAT → NonLivenessOfFreeChoicePetriNets |
#920 |
| RegisterSufficiency → SequencingToMinimizeMaximumCumulativeCost |
#475 |
| Partition → SequencingWithDeadlinesAndSetUpTimes |
#474 |
| ThreeDimensionalMatching → Numerical3DimensionalMatching |
#390 |
Direction error, broken parameter, or incorrect gadget (18)
| Source → Target |
Issue |
| DirectedTwoCommodityIntegralFlow → UndirectedTwoCommodityIntegralFlow |
#277 |
| Partition → IntegralFlowWithMultipliers |
#363 |
| VertexCover → MinimumCardinalityKey |
#459 |
| Clique → PartiallyOrderedKnapsack |
#523 |
| OptimalLinearArrangement → SequencingToMinimizeWeightedCompletionTime |
#472 |
| VertexCover → ComparativeContainment |
#385 |
| Partition/3Partition → ExpectedRetrievalCost |
#423 |
| MinimumHittingSet → AdditionalKey |
#460 |
| MinimumHittingSet → BoyceCoddNormalFormViolation |
#462 |
| VertexCover → MinimumCutIntoBoundedSets |
#250 |
| HamiltonianPath → ConsecutiveBlockMinimization |
#435 |
| HamiltonianPath → ConsecutiveSets |
#436 |
| MinimumCardinalityKey → PrimeAttributeName |
#461 |
| VertexCover → MultipleCopyFileAllocation |
#425 |
| MaximumClique → MinimumTardinessSequencing |
#206 |
| OptimalLinearArrangement → ConsecutiveOnesMatrixAugmentation |
#434 |
| Graph3Colorability → ConjunctiveQueryFoldability |
#463 |
| HamiltonianCircuit → BoundedComponentSpanningForest |
#238 |
Target instance unspecified / defers to literature (6)
| Source → Target |
Issue |
| 3SAT → MixedChinesePostman |
#260 |
| 3SAT → PathConstrainedNetworkFlow |
#364 |
| 3SAT → IntegralFlowWithHomologousArcs |
#365 |
| Satisfiability → UndirectedFlowWithLowerBounds |
#367 |
| 3SAT → MaximumLengthBoundedDisjointPaths |
#371 |
| MinVertexCover → ShortestCommonSupersequence |
#427 |
Incomplete derivation / unverified (8)
| Source → Target |
Issue |
Detail |
| 3SAT → RegisterSufficiency |
#872 |
Key register-gadget invariant only sketched |
| Planar3SAT → MinimumGeometricConnectedDominatingSet |
#377 |
Geometry still a sketch with symbolic delta |
| MinVertexCover → SchedulingWithIndividualDeadlines |
#478 |
Scheduling gadget omits padding/auxiliary tasks |
| MinVertexCover → MinimumDummyActivitiesInPERTNetworks |
#374 |
Unverified tier |
| MinVertexCover → SetBasis |
#383 |
Unverified tier |
| KColoring(K=3) → SparseMatrixCompression |
#431 |
Unverified tier |
| MinimumSetCovering → StringToStringCorrection |
#453 |
Unverified tier |
| PartialFeedbackEdgeSet → GroupingBySwapping |
#454 |
Unverified tier |
| 3SAT → RectilinearPictureCompression |
#458 |
Unverified tier |
| 3Partition → DynamicStorageAllocation |
#397 |
Needs guessed grouping map |
Summary
- 2 rules are potentially actionable (high/medium confidence)
- 6 rules have confirmed counterexamples — should be labeled "Wrong" on their issues
- 49 rules have various blocking issues (type mismatch, missing gadgets, direction errors, incomplete derivations)
Most low-confidence rules would require returning to the original papers and re-deriving the construction from scratch. They are recorded here so future contributors know what was examined and why each was skipped.
Source
