## NP-úplnost 3DM (z SAT) ##
**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$ )
::
:: 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\}$.
:: $\varphi$ splnitelná ⇔ v instanci $3DM$ ∃ PP.
* **Konstrukce 3DM ze SAT:**
1. Vytvoříme komponentu, která bude určovat, jakou hodnotu která proměnná dostane,
1. vytvoříme komponentu, která bude zajišťovat propojení této hodnoty s klauzulemi, v nichž se tato proměnná vyskytuje,
1. doplníme trojice tak, abychom dostali k splňujícímu ohodnocení skutečně perfektní párování a naopak.
* **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]$ do $X$ a $b_i\[1], \dots, b_i\[m]$ do $Y$. Do $W$ přidáme prvky $u_i\[1], \dots, u_i\[m]$ a $\overline u_i\[1], \dots, \overline u_i\[m]$.
:: Na těchto prvcích vytvoříme množiny trojic $T_i^f$ a $T_i^t$ takto (viz také obrázek):
:: $
\matrix{
T_i^t&=&\{(\overline u_i\[j], a_i\[j], b_i\[j])\;|\;1\leq j\leq m\}\cr
T_i^f&=&\{(u_i\[j], a_i\[(j+1)\;{\rm mod}\;m], b_i\[j])\;|\;1\leq j\leq m\}\cr
T_i&=&T_i^t\cup T_i^f\cr
}
$
:: Protože žádný z prvků $a_i\[j]$ ani $b_i\[j]$ se nebude vyskytovat v jiných trojicích, je tímto vynuceno, že PP buď musí obsahovat všechny trojice z $T_i^t$, nebo všechny trojice z $T_i^f$.
:: Pokud obsahuje trojice z $T_i^t$, znamená to, že žádná další vybraná trojice nesmí obsahovat literál $\overline u_i$, tedy vynucujeme hodnotu 1, true pro $u_i$, proto také $T_i^t$. Podobně pokud obsahuje perfektní párování trojice z $T_i^f$, vynucujeme hodnotu 0, false, odtud $T_i^f$.
* **Komponenta pro klauzule (clause satisfaction testing)** - bude zajišťovat propojení hodnoty proměnné s jejími klauzulemi
:: ∀ klauzuli $C_j$ přidáme nový prvek $s_1\[j]$ do množiny $X$, nový prvek $s_2\[j]$ do množiny $Y$ a množinu trojic
:: $
S_j=\{(u_i\[j], s_1\[j], s_2\[j])\;|\;u_i\in C_j\}\cup
\{(\overline u_i\[j], s_1\[j], s_2\[j])\;|\;\overline u_i\in C_j\}$
:: Prvky $s_1\[j]$ a $s_2\[j]$ se opět nebudou vyskytovat v jiných trojicích, díky tomu v perfektním párování musí být právě jedna trojice z množiny $S_j$.
:: Navíc pokud se trojice $(u_i\[j], s_1\[j], s_2\[j])$ vyskytuje v perfektním párování, znamená to, že $u_i\[j]$ se nemůže vyskytovat v jiné trojici a to znamená, že v tomto párování jsou všechny trojice z $T^t_i$ a žádná z $T_i^f$. Podobně by to bylo, kdyby v perfektním párování byla trojice s negativním literálem.
* **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\}$
* **Výsledek konstrukce:**
:: $
\matrix{
W&=&\{u_i\[j], \overline u_i\[j]\;|\;1\leq i\leq n, 1\leq j\leq m\}\cr
X&=&\{a_i\[j]\;|\;1\leq i\leq n, 1\leq j\leq m\}\;\cup\cr
&&\cup\;\{s_1\[j]\;|\;1\leq j\leq m\}\cr
&&\cup\;\{g_1\[j]\;|\;1\leq j\leq m(n-1)\}\cr
Y&=&\{b_i\[j]\;|\;1\leq i\leq n, 1\leq j\leq m\}\;\cup\cr
&&\cup\;\{s_2\[j]\;|\;1\leq j\leq m\}\cr
&&\cup\;\{g_2\[j]\;|\;1\leq j\leq m(n-1)\}\cr
M&=&\Big(\bigcup_{i=1}^nT_i\Big)\cup\Big(\bigcup_{j=1}^mS_j\Big)\cup
G\cr
}
$
:: Zřejmě platí, že $M\subseteq W\times X\times Y$, navíc $|M|=2mn+3m+2m^2n(n-1)$ a $|W|=|X|=|Y|=2mn$. 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.
:: Předpokládejme, že v $M$ existuje perfektní párování $M'$, na jehož základě zkonstruujeme ohodnocení $t$, které bude splňovat formuli $\varphi$. Nechť $i$ je libovolný index z $1, \dots, n$, jak jsme již zdůvodnili, v $M'$ jsou buď všechny trojice z $T_i^t$, nebo všechny trojice z $T_i^f$, pokud $M'$ obsahuje trojice z $T_i^t$, definujeme $t(u_i):=1$, pokud $M'$ obsahuje trojice z $T_i^f$, definujeme $t(u_i):=0$. Nechť $C_j$ je libovolná klauzule formule $\varphi$, množina $M'$ musí obsahovat právě jednu z trojic z $S_j$, neboť to je jediná možnost, jak mohou být pokryty prvky $s_1\[j]$ a $s_2\[j]$ a dvě obsahovat nemůže, protože každý z těchto prvků musí být pokryt právě jednou. Nechť tato trojice je $(u_i\[j], s_1\[j], s_2\[j])$ pro nějaké $i=1, \dots, n$. To znamená, že $u_i$ je proměnná, vyskytující se jako pozitivní literál v klauzuli $C_j$, navíc musí platit, že $u_i\[j]$ se nemůže vyskytovat v žádné jiné trojici v $M'$, a proto $M'$ obsahuje trojice z $T_i^t$ a nikoli trojice z $T_i^f$, a tedy $t(u_i)=1$, čímž je klauzule $C_j$ splněna. Podobně bychom postupovali v případě, kdy trojicí v $S_j\cap M'$ by byla $(\overline{u_i}\[j], s_1\[j], s_2\[j])$, tedy pokud by obsahovala negativní literál, jediný rozdíl by byl, že bychom dostali, že $t(u_i)=0$ a že $C_j$ je splněna díky negativnímu literálu $\overline{u_i}$.
:: Pokud je naopak $\varphi$ splnitelná, zkonstruujeme perfektní párování následovně. Nechť $t:U\mapsto\{0, 1\}$ je ohodnocení splňující $\varphi$ a nechť $z_j$ označuje literál, který je v $C_j$ tímto ohodnocením splněn pro $j=1, \dots, m$. Pokud je takových literálů víc, vybereme prostě jeden z nich.
:: Pak položíme $M'=\Big(\bigcup_{t(u_i)=1}T_i^t\Big)\cup
\Big(\bigcup_{t(u_i)=0}T_i^f\Big)\cup
\Big(\bigcup_{j=1}^m\{(z_j\[j], s_1\[j], s_2\[j])\}\Big)
\cup G',
$ kde $G'$ je množina vhodně vybraných trojic z $G$, které doplňují párování o pokrytí zbylých literálů.
:: Není těžké ověřit, že takto definovaná množina $M'$ tvoří perfektní párování $M$.