## NP-úplnost 3DM (z SAT) ##

![3dm_io.jpg](Archiv/Řešené otázky NTIN090/3DM23SAT/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$.

Dk($3DM ∈ NPC \Leftarrow 3SAT\leq_m^p 3DM$ )
:: 

**Splnitelnost formule v 3KNF (3SAT)**

* **Instance:** Formule φ na n proměnných v 3KNF, tj. KNF, v níž každá klauzule obsahuje !3 literály.
* **Otázka:** ∃ ohodnocení, pro které je φ  splněná?

We will use sets with 3 elements to visualize triples:

:: ![](Archiv/Řešené otázky NTIN090/3DM23SAT/3dmtri.png){: alt="3dmtri.png"}

**3SAT 3DM**

* variables x1, · · · , xn → variables xj3, aj3, b2j , c1k
* literals x1, ¬x1 → variables xj1, ¬xj1
* clauses Cj = (x1 ∨ ¬x2 ∨ ¬x3) → triples (xj1, b1j , b2j) (¬xj3, b1j , b2j)
* “There exists a sat truth assignment”. → ”There is a matching”

**“There is a truth assignment T”**

* ∃T : {x1, · · · , xn} → {TRUE, FALSE}
* T(xi) = TRUE ⇔ T(¬xi) = FALSE

The second property is easily translated to the 3DM-world:

:: ![](Archiv/Řešené otázky NTIN090/3DM23SAT/3dmmarr.png){: alt="3dmmarr.png"}
:: T(Xi) = TRUE → xi is not “married”

A literal xi can be used inmany clauses. In 3DM wemust have asmany copies of xi as there are clauses:

:: ![](Archiv/Řešené otázky NTIN090/3DM23SAT/3dmkopie.png){: alt="3dmkopie.png"}

* Either all the black triples must be chosen (“married”) or all the red ones!
* If T(xi) = TRUE then we choose all the red triples, and the black copies of xi are free to be used later in the reduction. And vice versa.
* We make one such **truth setting component** for each variable $x_i$ in 3SAT.

**“T is satisfying”**

:: We translate each clause (example: Cj = (x1 ∨ ¬x2 ∨ ¬x3)) into 3 triples:
:: ![](Archiv/Řešené otázky NTIN090/3DM23SAT/3dm3triples.jpg){: alt="3dm3triples.jpg"}

* b1 j and b2 j can bemarried if and only if at least one of the literals in Cj is notmarried in the truth setting component.
* If we have a satisifiable 3SAT-instance , then all b1j and b2j-variables (1 ≤ j ≤ m) can be married.
* If we have a negative 3SAT-instance , then some b1 j and b2 j-variables will not be married.

**Cleaning up (“Garbage collection”)**

:: There are many xji who are neither married in the truth settting components nor in the “clause-satisfying” part. We introduce a number of fresh c-variables who canmarry “everybody”:

![](Archiv/Řešené otázky NTIN090/3DM23SAT/3dmgarbage.jpg){: alt="3dmgarbage.jpg"}

* There are m × n unmarried x-variables after the truth setting part. 
* If all m clauses are satisfiable then there will remain (m × n) − m = m(n − 1) unmarried x-variables.
* So we let 1 ≤ k ≤ m(n − 1).

Zdroje
:: 

* http://www.uio.no/studier/emner/matnat/ifi/INF4130/h12/undervisningsmateriale/dino4.pdf