next up previous contents
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:
\begin{pagi}{34}Un subconjunto \begin{displaymath}M\subset X\times Y\times Z,\en...
...es conjuntos, ajenos a pares, de una misma cardinalidad, digamos $n$ .\end{pagi}
Solución:
\begin{pagi}{34}$\left\{\begin{array}{ll}
1 &\mbox{\rm si hay un atercetamiento...
...ce tercetas, } \\
0 &\mbox{\rm en otro caso. }
\end{array}\right.$\end{pagi}



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


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: Se tiene que

\begin{displaymath}M'=M_{10}\cup M_{11}\cup M_{2}\cup M_{3}\end{displaymath}

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 Puesto que M' contiene 2nm tercetas las anteriores cotas se alcanzan efectivamente. Las del tipo M1 son de la forma

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

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

\begin{displaymath}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.\end{displaymath}

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 M2 en M'.
next up previous contents
Siguiente: Partición Un nivel arriba: Atercetamientos Anterior: Atercetamientos
Guillermo Morales-Luna
2000-07-10