<!-- Image:3dm_io.jpg--> 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í?

Image:3dmpromenne.png

{{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) ::

:: 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

:: <u>∀ proměnnou</u> $u_i$, $i=1, \dots, n$ přidáme nové vnitřní prvky

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 4: a_i\̲[̲1], \dots, a_i\…

a

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 4: b_i\̲[̲1], \dots, b_i\…

a

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 4: u_i\̲[̲1], \dots, u_i\…

. :: 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).

![$ do trojic v množiny $S_j

ParseError: KaTeX parse error: Expected '}', got 'EOF' at end of input: …do=get){: 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

:: <u>∀ klauzuli $C_j$</u> přidáme nové prvky

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 4: s_1\̲[̲j]∈X

a

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 4: s_2\̲[̲j]∈Y

a množinu trojic $S_j$. :: Prvky

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 4: s_1\̲[̲j]

a

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 4: 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

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 5: (u_i\̲[̲j], s_1\[j], s_…

v perfektním párování ⇒ v PP $M'$ je celá $T^t_i$ (podobně pro negaci).

Image:3dmgarbage.png

• 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ů

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 4: u_i\̲[̲j], \overline u…

, $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

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 4: g_1\̲[̲k]

a do $Y$ prvky

ParseError: KaTeX parse error: Undefined control sequence: \[ at position 4: 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

}}