Section III, p. 385 — a polynomial-time reduction from THREE-DIMENSIONAL MATCHING makes a problem NP-hard
ProvedIntractableCoding.Weights.npHard_of_threeDM_reductionLet be a decision problem on instances of a type , presented through a binary encoding . Suppose maps every THREE-DIMENSIONAL MATCHING instance to an instance of , is computed by a polynomial-time multi-stack Turing machine from the encoding of to , and satisfies
Then is NP-hard with respect to .
This is the step "a polynomial-time algorithm for COSET WEIGHTS implies a polynomial-time algorithm for THREE-DIMENSIONAL MATCHING, which in turn implies a polynomial-time algorithm for every NP-problem", used once for each of the two coding problems. It rests on the NP-hardness of THREE-DIMENSIONAL MATCHING (Karp's problem 17), published as PricingWithTips.threeDM_np_hard.
Differences from the source:
- generalization: the reduction to COSET WEIGHTS (and the same argument for SUBSPACE WEIGHTS) → any target problem P with any binary encoding enc; reason: the paper uses the argument twice with the same shape; taking enc = encodeCoset, P = CosetWeightsYes (resp. encodeSubspace, SubspaceWeightsYes) gives exactly the paper's two uses
- reading: a polynomial-time algorithm for COSET WEIGHTS implies one for every NP-problem (Turing style) → NP-hardness under polynomial-time TM2-computed many-one reductions; reason: the paper's reduction is a many-one map and its notion of NP-completeness is Karp's [4]; many-one hardness implies the Turing-style sentence
import Mathlib import Definitions.Def_IntractableCoding_Weights_NPComplete
namespace IntractableCoding.Weights
open PricingWithTips
/-- NP-hardness transfers along a polynomial-time many-one reduction from
THREE-DIMENSIONAL MATCHING: if a map `g` from 3DM instances to instances of `P`, computed by a
polynomial-time TM2 machine from `encodeThreeDMInstance I` to `enc (g I)`, satisfies
`ThreeDMYes I ↔ P (g I)` for every `I`, then `P` is NP-hard (with respect to `enc`). -/
theorem npHard_of_threeDM_reduction {α : Type} (enc : α → List Bool) (P : α → Prop)
(g : ThreeDMInstance → α)
(hg : Nonempty (Turing.TM2ComputableInPolyTime encodeThreeDMInstance enc g))
(hred : ∀ I : ThreeDMInstance, ThreeDMYes I ↔ P (g I)) :
NPHardFor enc P := by sorry
end IntractableCoding.Weights
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.