**Trojrozměrné párování (3-dimensional matching - 3DM)** * **Instance:** Množina $M⊆ W\times X\times Y$, kde $W, X, Y$ jsou po dvou disjunktní množiny a $|W|= |X|= |Y| = q$. * **Otázka:** Obsahuje $M$ perfektní párování? Jinými slovy, existuje množina $M'⊆ M$, $|M'| = q$, trojice v níž obsažené jsou po dvou disjunktní?  {{theorem | 3DM je NP-úplný problém. | 3DM ∈ NPC }} Dk($3DM ∈ NP$) :: :: plyne z toho, že pokud máme k dispozici množinu $M'⊆ M$, dokážeme ověřit v polynomiálním čase, jde-li o párování velikosti $|M'| = q$. Dk($3DM ∈ NPC \Leftarrow SAT\leq_m^p 3DM$ - neformální konstrukce 3DM ze SAT, [zde je formálnější přepis ze skript](Řešené_otázky_NTIN090/3DM2SAT)) :: :: Nechť $\varphi=C_1\wedge C_2\wedge\dots\wedge C_m$ je formule (z klauzulí $C_i$) v KNF na proměnných $U=\{u_1, \dots, u_n\}$. * **Komponenta pro proměnné (truth-setting)** - bude určovat, jakou hodnotu která proměnná dostane :: ∀ proměnnou $u_i$, $i=1, \dots, n$ přidáme nové vnitřní prvky $a_i\[1], \dots, a_i\[m]∈X$ a $b_i\[1], \dots, b_i\[m]∈Y$ a $u_i\[1], \dots, u_i\[m], \overline u_i\[1], \dots, \overline u_i\[m]∈W$. :: Na těchto prvcích vytvoříme množiny trojic $T_i^f$ a $T_i^t$ takto (viz také obrázek). :: PP $M'$ buď musí obsahovat všechny trojice z $T_i^t$ (vynucuje TRUE pro proměnnou), nebo všechny trojice z $T_i^f$ (vynucuje FALSE pro proměnnou). {: alt="$ do trojic v množiny $S_j$."} * **Komponenta pro klauzule (clause satisfaction testing)** - bude zajišťovat propojení hodnoty proměnné s jejími klauzulemi :: ∀ klauzuli $C_j$ přidáme nové prvky $s_1\[j]∈X$ a $s_2\[j]∈Y$ a množinu trojic $S_j$. :: Prvky $s_1\[j]$ a $s_2\[j]$ se opět nebudou vyskytovat v jiných trojicích, díky tomu v PP $M'$ musí být !1 trojice z množiny $S_j$. :: Pokud je $(u_i\[j], s_1\[j], s_2\[j])$ v perfektním párování ⇒ v PP $M'$ je celá $T^t_i$ (podobně pro negaci).  * **Komponenta pro doplnění trojic (garbage collection)** - abychom dostali k splňujícímu ohodnocení skutečně PP a naopak :: Těmito trojicemi jsme ale schopni v PP pokrýt jen $mn+n$ prvků z $2mn$ prvků $u_i\[j], \overline u_i\[j]$, $i=1, \dots, n$, $j=1, \dots, m$. Z toho $mn$ jich pokryjeme trojicemi z $T_i^t$ nebo $T_i^f$, $i=1, \dots, n$. Trojicemi z $S_j$, $j=1, \dots, m$ pokryjeme dalších $m$ prvků. :: Zbývá tedy $2mn-(mn+m)=m(n-1)$ prvků, jež nejsme zatím schopni pokrýt, proto přidáme do množiny $M$ trojice, které nám jejich pokrytí zabezpečí. :: Do $X$ přidáme prvky $g_1\[k]$ a do $Y$ prvky $g_2\[k]$ obojí pro $k=1, \dots, m(n-1)$ a do $M$ přidáme množinu trojic :: $G=\{(u_i\[j], g_1\[k], g_2\[k]), (\overline u_i\[j], g_1\[k], g_2\[k])\;|\;1\leq k\leq m(n-1), 1\leq i\leq n, 1\leq j\leq m\}$ :: Zřejmě platí, že $M\subseteq W\times X\times Y$ a $|W|=|X|=|Y|=2mn=q$. :: Velikost takto vytvořené instance trojrozměrného párování je tedy polynomiálně velká a v polynomiálním čase ji zřejmě lze i vytvořit. {{Zdroje| * http://ktiml.mff.cuni.cz/~kucerap/NTIN090/NTIN090-poznamky.pdf * http://www.uio.no/studier/emner/matnat/ifi/INF4130/h12/undervisningsmateriale/dino4.pdf }}