Three-dimensional matching is NP-hard
ProvedPricingWithTips.threeDM_np_hardcomputational-complexitymatching
Perfect three-dimensional matching is NP-hard: every language with polynomial-size certificates checkable by a polynomial-time Turing machine has a polynomial-time many-one reduction to deciding whether a finite three-partite 3DM instance has a perfect matching. Instances are represented by a unary size prefix and a cubic Boolean incidence table.
Preamble
import Definitions.Def_PricingWithTips_NPHardness
Formal statement
namespace PricingWithTips theorem threeDM_np_hard : NPHardMarketPredicate ThreeDMYes := by sorry end PricingWithTips
Source
Karp, Reducibility Among Combinatorial Problems (1972), 3-dimensional matching; cited in Pricing with Tips in Three-Sided Delivery Platforms, arXiv:2507.10872v1, Theorem 4.1 proof
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.