.

Siguiente: Raices de módulo 1 Un nivel arriba: MCD no trivial Anterior: MCD no trivial

.

Comentario: 3SAT se transforma en este problema. Se ignora si acaso pertenece a NP o a co-NP. Se mantiene como un problema difícil-NP aún cuando $\forall i,j: a_{ij}\in \{-1,+1\}$ , o m=2. El problema es, sin embargo, seudo-polinomial en tiempo. En la misma situación está el siguiente problema:

Instancia:
$\begin{pagi}{34} $m$\space sucesiones de parejas $A_i=\{(a_{ij},b_{ij})\}_{j=1,\ldots,n}\subset Z^2$\space tales que $b_{ij}\geq 0$ , y $K>0$ . \end{pagi}$
Solución:
$\begin{pagi}{34} Decidir si acaso \begin{displaymath}\mbox{\rm MCD}\left\{\sum... ...ots, m\right\}\mbox{\rm posee grado a lo sumo $K$}.\end{displaymath} \end{pagi}$

Guillermo Morales-Luna
2000-07-10