Algoritmos aleatorizados com oráculo para MCSP: aplicações para o problema do resíduo quadrático e do logaritmo discreto

Neste artigo estudamos a relação entre três problemas que são candidatos a serem NP-intermediários. Mais precisamente, apresentamos explicitamente dois algoritmos polinomiais aleatorizados que fazem acesso à um oráculo para o problema de minimização de circuitos. O primeiro algoritmo resolve o problema do resíduo quadráico e o segundo o problema do logaritmo discreto.