การจับคู่เชิงตัวเลขสามมิติเป็นปัญหาการตัดสินใจNP-complete โดยกำหนดด้วยมัลติเซตของจำนวนเต็ม สามเซต , และแต่ละเซตประกอบด้วยองค์ประกอบ และขอบเขตเป้าหมายคือการเลือกซับเซตของโดยที่จำนวนเต็มทุกตัวในและ ปรากฏเพียงครั้งเดียว และสำหรับทุกสามตัวในซับเซต เป็นจริง ปัญหานี้ถูกระบุว่าเป็น [SP16] ใน^{[ 1 ]}${\displaystyle X}$${\displaystyle Y}$${\displaystyle Z}$${\displaystyle k}$${\displaystyle b}$${\displaystyle M}$${\displaystyle X\times Y\times Z}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle Z}$${\displaystyle (x,y,z)}$${\displaystyle x+y+z=b}$

พิจารณา, และ, และกรณีนี้มีคำตอบ นั่นคือสังเกตว่าผลรวมของแต่ละสามตัวเลขเท่ากับเซตไม่ใช่คำตอบด้วยเหตุผลหลายประการ: ไม่ได้ใช้ทุกตัวเลข ( ขาด a) มีการใช้ตัวเลขมากเกินไป ( ) และผลรวมของแต่ละสามตัวเลขไม่เท่ากับ(เนื่องจาก) อย่างไรก็ตาม มีคำตอบอย่างน้อยหนึ่งคำตอบสำหรับปัญหานี้ ซึ่งเป็นคุณสมบัติที่เราสนใจในปัญหาการตัดสินใจ หากเราใช้, และสำหรับค่าเดียวกันปัญหานี้จะไม่มีคำตอบ (ผลรวมของตัวเลขทั้งหมดเท่ากับซึ่งไม่เท่ากับในกรณีนี้) ${\displaystyle X=\{3,4,4\}}$${\displaystyle Y=\{1,4,6\}}$${\displaystyle Z=\{1,2,5\}}$${\displaystyle b=10}$${\displaystyle \{(3,6,1),(4,4,2),(4,1,5)\}}$${\displaystyle b=10}$${\displaystyle \{(3,6,1),(3,4,2),(4,1,5)\}}$${\displaystyle 4\in X}$${\displaystyle 3\in X}$${\displaystyle b}$${\displaystyle 3+4+2=9\neq b=10}$${\displaystyle b=11}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle Z}$${\displaystyle 30}$${\displaystyle k\cdot b=33}$

ทุกกรณีของปัญหาการจับคู่สามมิติเชิงตัวเลข ล้วนเป็นกรณีของทั้งปัญหาการแบ่งส่วนสามมิติและปัญหา การจับคู่สามมิติ

กำหนดให้ตัวอย่างของการจับคู่ 3 มิติเชิงตัวเลข สร้างไฮเปอร์กราฟ สามส่วน ที่มีด้าน, และโดยที่ไฮเปอร์เอดจ์⁠ ⁠ ก็ต่อเมื่อการจับคู่ในไฮเปอร์กราฟนี้สอดคล้องกับคำตอบของการแบ่งส่วน ABC ${\displaystyle X}$${\displaystyle Y}$${\displaystyle Z}$${\displaystyle (x,y,z)}$${\displaystyle x+y+z=T}$

ปัญหาการจับคู่ 3 มิติเชิงตัวเลขคือปัญหา [SP16] ของ Garey และ Johnson ^{[ 1 ]}พวกเขาอ้างว่าเป็น NP-complete และอ้างอิงถึง^{[ 2 ]}แต่ข้ออ้างดังกล่าวไม่ได้รับการพิสูจน์ในแหล่งข้อมูลนั้น ความยากแบบ NP ของปัญหาที่เกี่ยวข้องคือการแบ่ง 3 ส่วนได้รับการพิสูจน์ใน^{[ 1 ]}โดยการลดรูปจากการจับคู่ 3 มิติผ่านการแบ่ง 4 ส่วน เพื่อพิสูจน์ความสมบูรณ์แบบของ NP ของการจับคู่ 3 มิติเชิงตัวเลข การพิสูจน์ควรจะคล้ายกัน แต่ควรใช้การลดรูปจากการจับคู่ 3 มิติผ่านปัญหาการจับคู่ 4 มิติเชิงตัวเลข การพิสูจน์ความยากแบบ NP อย่างชัดเจนมีอยู่ในเอกสารฉบับต่อมา:

• Yu, Hoogeveen และLenstra ^{[ 3 ]}พิสูจน์ความยากแบบ NP ของการจับคู่ 3 มิติเชิงตัวเลขเวอร์ชันที่จำกัดมาก ซึ่งเซตสองในสามเซตประกอบด้วยตัวเลข 1,..., k เท่านั้น
• Caracciolo, Fichera และ Sportiello ^{[ 4 ]}พิสูจน์ความยากแบบ NP ของการจับคู่ 3 มิติเชิงตัวเลขและปัญหาที่เกี่ยวข้องโดยการลดจากNAE-SATการลดนั้นเป็นเชิงเส้นนั่นคือ ขนาดของอินสแตนซ์ที่ลดลงเป็นฟังก์ชันเชิงเส้นของขนาดของอินสแตนซ์ดั้งเดิม