Siguiente: Ecuaciones algebraicas en el Un nivel arriba: Divisibilidad de expresiones exponenciales Anterior: Divisibilidad de expresiones exponenciales

.

Comentario: 3SAT se transforma en este problema. Se desconoce si acaso este problema está en NP o en co-NP. Sin embargo es seudo-polinomial en tiempo, es decir, de complejidad polinomial si sus entradas se escriben en unario. Aún para cada q, con |q|>1, y suponiendo que los coeficientes a_i o b_i son productos de primos distintos, se tiene un problema difícil-NP.