Numerická trojrozměrná shoda - Numerical 3-dimensional matching

Numerická trojrozměrná shoda je NP-kompletní rozhodovací problém. Je to dáno třemi multisety z celá čísla ${ displaystyle X}$, ${ displaystyle Y}$ a ${ displaystyle Z}$, z nichž každý obsahuje ${ displaystyle k}$ prvky a vázaný ${ displaystyle b}$. Cílem je vybrat podmnožinu ${ displaystyle M}$ z ${ displaystyle X krát Y krát Z}$ tak, že každé celé číslo v ${ displaystyle X}$, ${ displaystyle Y}$ a ${ displaystyle Z}$ nastane přesně jednou a to pro každou trojku ${ displaystyle (x, y, z)}$ v podmnožině ${ displaystyle x + y + z = b}$ Tento problém je označen jako [SP16] v.^[1]

Příklad

Vzít ${ displaystyle X = {3,4,4 }}$, ${ displaystyle Y = {1,4,6 }}$ a ${ displaystyle Z = {1,2,5 }}$, a ${ displaystyle b = 10}$. Tato instance má řešení, a to ${ displaystyle {(3,6,1), (4,4,2), (4,1,5) }}$. Všimněte si, že každá trojitá částka je ${ displaystyle b = 10}$. Sada ${ displaystyle {(3,6,1), (3,4,2), (4,1,5) }}$ není řešením z několika důvodů: nepoužívá se každé číslo (a ${ displaystyle 4 v X}$ chybí), číslo se používá příliš často ( ${ displaystyle 3 v X}$) a ne každá trojitá částka ${ displaystyle b}$ (od té doby ${ displaystyle 3 + 4 + 2 = 9 neq b = 10}$). Existuje však alespoň jedno řešení tohoto problému, kterým je vlastnost, která nás zajímá s problémy s rozhodováním ${ displaystyle b = 11}$ za stejné ${ displaystyle X}$, ${ displaystyle Y}$ a ${ displaystyle Z}$, tento problém by neměl řešení (všechna čísla se sčítají do ${ displaystyle 30}$, což se nerovná ${ displaystyle k cdot b = 33}$ v tomto případě).

Související problémy

Každá instance problému Numerické 3-dimenzionální shody je instancí obou Problém se 3 oddíly a 3-dimenzionální shoda problém.

Důkaz úplnosti NP

NP-úplnost problému se 3 oddíly uvádí Garey a Johnson v dokumentu „Computers and Intractability; A Guide to The Theory of NP-Completeness“, který odkazuje na tento problém pomocí kódu [SP16].^[1] Dělá se to redukcí z 3-dimenzionálního párování přes 4-oddíl. K prokázání NP-úplnosti numerického 3-dimenzionálního párování je důkaz podobný, ale redukce z 3-dimenzionálního párování pomocí numerického 4-dimenzionálního párování by měly být použity.

Reference