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

Divisibilidad de expresiones exponenciales




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$\space y un entero $q\in N$ . \end{pagi}
Solución:
\begin{pagi}{34} Decidir si acaso \begin{displaymath}\prod_{i=1}^n(q^{a_i}-1)\vert\prod_{j=1}^m(q^{b_j}-1).\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