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

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:

:: 3dmtri.png does not exist. Create it?{: 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:

:: 3dmmarr.png does not exist. Create it?{: 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:

:: 3dmkopie.png does not exist. Create it?{: 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: :: 3dm3triples.jpg does not exist. Create it?{: 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”:

3dmgarbage.jpg does not exist. Create it?{: 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