.

Siguiente: MCD no trivial Un nivel arriba: No-divisibilidad de un producto Anterior: No-divisibilidad de un producto

.

Comentario: 3SAT se transforma en este problema. Aquí, el demostrar la pertenencia a NP es la parte más complicada. El siguiente problema similar es también completo-NP:

Instancia:
$\begin{pagi}{34} $m$\space parejas $A=\{(a_{i},b_{i})\}_{i=1,\ldots, m}\subset Z^2$\space tales que $b_{ij}\geq 0$ . \end{pagi}$
Solución:
$\begin{pagi}{34} Decidir si acaso \begin{displaymath}\prod_{i=1}^m(X^{a_{i}}-1)\vert\prod_{i=1}^m(X^{b_{i}}-1).\end{displaymath} \end{pagi}$

Guillermo Morales-Luna
2000-07-10