Siguiente: Partición Un nivel arriba: Atercetamientos Anterior: Atercetamientos

Atercetamientos (3DM):

Este problema, llamado en inglés 3-dimensional matching, se formaliza como sigue,


Instancia:

Solución:




Naturalmente, más que planteado como un problema de decisión 3DM se plantea como uno de solución. Así que en caso de que hubiera un tal atercetamiento, habría que localizarlo explícitamente. Proposición: 3DM es completo-NP. Demostración: Que este problema esté en NP es fácil de ver:

1.

Se conjetura un posible atercetamiento M' incluído en M, con n tercetas.

2.

Se revisa que cada una de las proyecciones cubra a los conjuntos ``coordenadas''.

Para probar que es difícil-NP, veamos que 3SAT se reduce a 3DM. Dados

• $\mbox{\bf X}=\{X_1,\ldots,X_n\}$: conjunto de n variables proposicionales,
• $\mbox{\bf C}=\{c_1,\ldots,c_m\}$: conjunto de m cláusulas de 3 literales sobre $\mbox{\bf X}$,

construiremos una instancia de 3DM de manera que ésta dé una instancia con respuesta positiva en 3DM si y sólo si la forma conjuntiva $\mbox{\bf C}$ es satisfactible. En tal caso, un atercetamiento en la instancia construída ha de determinar una asignación de valores de verdad a las variables en $\mbox{\bf X}$ que satisfaga a $\mbox{\bf C}$. Definamos

• $X=\left\{x_{ij},\bar{x}_{ij}\vert 1\leq i\leq m,1\leq j\leq n\right\}$: Tiene 2nm elementos.
• $Y=A_1\cup S_1\cup G_1$ donde
  • $A_1=\left\{a_{1ij}\vert 1\leq i\leq m,1\leq j\leq n\right\}$: Tiene nm elementos.
  • $S_1=\left\{s_{1i}\vert 1\leq i\leq m\right\}$: Tiene m elementos.
  • $G_1=\left\{g_{1k}\vert 1\leq k\leq m(n-1)\right\}$: Tiene m(n-1) elementos.
• $Z=A_2\cup S_2\cup G_2$ donde
  • $A_2=\left\{a_{2ij}\vert 1\leq i\leq m,1\leq j\leq n\right\}$: Tiene nm elementos.
  • $S_2=\left\{s_{2i}\vert 1\leq i\leq m\right\}$: Tiene m elementos.
  • $G_2=\left\{g_{2k}\vert 1\leq k\leq m(n-1)\right\}$: Tiene m(n-1) elementos.
  Consecuentemente, tanto Y como Z poseen 2nm elementos cada uno.
• Tercetas de asignación: Para cada variable X_j construímos los conjuntos de tercetas
  
  $$\begin{eqnarray*}V_j^{\mbox{\it verda}} &=& \left\{[\bar{x}_{ij},a_{1ij},a_{2ij}... ...\\ V_j &=& V_j^{\mbox{\it verda}} \cup V_j^{\mbox{\it falso}} \end{eqnarray*}$$
  
  El propósito de esta definición es que todo atercetamiento M' con 2nm tercetas debe satisfacer las condiciones siguientes:
  
  $$\begin{eqnarray*}(1&\Rightarrow)&M'\cap V_j\not=\emptyset \\ M'\cap V_j^{\mbox... ...ghtarrow& M'\cap V_j^{\mbox{\it falso}}=V_j^{\mbox{\it falso}} \end{eqnarray*}$$
  
  así pues, un tal atercetamiento fuerza de manera natural un valor de verdad en la variable X_j.
• Tercetas de satisfacción: Para cada cláusula c_i construímos el conjunto
  
  $$C_i=\left\{[x_{ij},s_{1ij},s_{2ij}]\vert X_j\in c_i\right\} \... ...t\{[\bar{x}_{ij},s_{1ij},s_{2ij}]\vert\bar{X}_j\in c_i\right\}.$$
  
  

• Tercetas de relleno: Construímos el conjunto
  
  $$G=\left\{[x_{ij},g_{1ij},g_{2ij}],[\bar{x}_{ij},s_{1ij},s_{2i... ...k\leq m(n-1) \\ 1\leq i\leq m \\ 1\leq j\leq n \end{array}}} .$$
  
  

• Instancia para 3DM:
  
  $$M=\left(\bigcup_{j=1}^n V_j\right) \cup\left(\bigcup_{i=1}^m C_i\right) \cup G.$$
  
  
  Consecuentemente, $\mbox{\rm card}(M)=2mn+3m+2m^2n(n-1).$

Soluciones de 3SAT corresponden a soluciones de 3DM: Supongamos que la asignación $\mbox{\boldmath$\epsilon$ }:X_j\mapsto \epsilon_j$ satisface a la forma conjuntiva C. Consideremos las siguientes tercetas:

• $M_{10}={\displaystyle \bigcup_{\epsilon_j=0}} V_j^{\mbox{\it falso}}$: Esto da $n_f\cdot m$ tercetas, donde n_f es el número de 0's en la asignación $\mbox{\boldmath$\epsilon$ }$.
• $M_{11}={\displaystyle \bigcup_{\epsilon_j=1}} V_j^{\mbox{\it verda}}$: Esto da $n_v\cdot m$ tercetas, donde n_v es el número de 1's en la asignación $\mbox{\boldmath$\epsilon$ }$. Evidentemente $(n_f+n_v)\cdot m=n\cdot m$.
• Para cada cláusula c_i elijamos una literal $z_{i}\in \mbox{\bf X}\cup\bar{\mbox{\bf X}}$ que haga que c_i sea verdadera, es decir tal que $z_{i}(\epsilon_{z_i})=1$. Tal literal existe porque la asignación satisface a todas las cláusulas. Sea entonces
  
  $$M_2=\bigcup_{i=1}^m \{[z_{i},s_{1i},s_{2i}]\}.$$
  
  
  Este conjunto consta de m tercetas.
• M₃ es un subconjunto de tercetas de la forma [y,g_1k,g_2k] donde y varía sobre todas las literales que no hayan aparecido en los conjuntos de arriba, de las cuales hay precisamente
  
  2nm-(nm+m)=(n-1)m
  
  
  y los g's varían sobre todas sus posibilidades (la formación de apareamientos buenos entre parejas de g's es trivial).

Se tiene que

$$M'=M_{10}\cup M_{11}\cup M_{2}\cup M_{3}$$

es un atercetamiento de 2nm tercetas incluído en la instancia M.


Soluciones de 3DM corresponden a soluciones de 3SAT: Sea M' un atercetamiento en M con 2nm elementos. Por la construcción de las tercetas, necesariamente

• A lo más (n-1)m tercetas de M' son del tipo M₃,
• a lo más m tercetas de M' son del tipo M₂, y
• a lo más nm tercetas de M' son del tipo M₁.

Puesto que M' contiene 2nm tercetas las anteriores cotas se alcanzan efectivamente. Las del tipo M₁ son de la forma

$$\bigcup_{j\in J_0}V_j^{\mbox{\it falso}}\cup \bigcup_{j\in J_1}V_j^{\mbox{\it verda}},$$

donde $J_0\cup J_1=[1,n]$. Pues bien la asignación

$$X_j\mapsto\left\{\begin{array}{ll} 1 &\mbox{\rm si $j\in J_1$, } \\ 0 &\mbox{\rm si $j\in J_0$. } \end{array}\right.$$

satisface a la instancia de 3SAT. En cada cláusula la literal que se satisface es la que aparece en la correspondiente terceta del tipo M₂ en M'.
Siguiente: Partición Un nivel arriba: Atercetamientos Anterior: Atercetamientos