NP-úplnost 3DM (z SAT)

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í?

{{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$.

Image:3dm.jpg

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,

  2. vytvoříme komponentu, která bude zajišťovat propojení této hodnoty s klauzulemi, v nichž se tato proměnná vyskytuje,

  3. 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

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

do $X$ a

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

do $Y$. Do $W$ přidáme prvky

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

a

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

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

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

ani

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

Image:3dm3triples.jpg

• 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ý prvek

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

do množiny $X$, nový prvek

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

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 perfektním párování musí být právě jedna trojice z množiny $S_j$. :: Navíc pokud se trojice

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

vyskytuje v perfektním párování, znamená to, že

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

Image:3dmgarbage.jpg

• 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}$

• 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

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]

a dvě obsahovat nemůže, protože každý z těchto prvků musí být pokryt právě jednou. Nechť tato trojice je

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

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

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

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

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