Algoritmos aleatorizados com oráculo para MCSP: aplicações para o problema do resíduo quadrático e do logaritmo discreto - Sdroievski, Nicollas M.; da Silva, Murilo V. G. (Anais do Encontro de Teoria da Computação (ETC); 2016: Anais do I Encontro de Teoria da Computação, 2016)
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.