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

Incongruencias simultáneas




Instancia:
\begin{pagi}{34} Un subconjunto de parejas $P=\{(a_i,b_i)\}_{i=1,\ldots,n}\subset N^2$ . \end{pagi}
Solución:
\begin{pagi}{34} Un entero $x$\space tal que \begin{displaymath}\forall i\leq n:\;x\not\equiv a_i \mbox{\rm mod } b_i.\end{displaymath} \end{pagi}



Referencia: Stockmeyer, Meyer: ``Word problems requiring exponential time'', Proc. 5th Ann. ACM Symp. on Theory of Computing, ACM New York, 1-9, 1973.
 
Guillermo Morales-Luna
2000-07-10