next up previous contents
Siguiente: . Un nivel arriba: Algunos otros problemas Anterior: .

Comparación de factores de divisibilidad




Instancia:
\begin{pagi}{34} Dos vectores $\mbox{\bf a}=(a_1,\ldots,a_n)\in N^n$\space y $\mbox{\bf b}=(b_1,\ldots,b_m)\in N^m$ . \end{pagi}
Solución:
\begin{pagi}{34} Un entero $c$\space tal que \begin{displaymath}\mathop{\rm Min}_{c\vert a_i} i\geq \mathop{\rm Min}_{c\vert b_i} i.\end{displaymath} \end{pagi}



Referencia: Plaisted: ``Some polynomial and integer divisibility problems are NP-hard'', Proc. 17th Ann. Symp. on Foundations of Computer Science IEEE Computer Society, 264-267, 1976.
 
Guillermo Morales-Luna
2000-07-10