Open AccessAlgoritmos aleatorizados com oráculo para MCSP: aplicações para o problema do resíduo quadrático e do logaritmo discreto
Author(s) -
Nicollas M. Sdroievski,
Murilo V. G. da Silva
Publication year - 2016
Language(s) - Portuguese
Resource type - Conference proceedings
DOI - 10.5753/etc.2016.9842
Subject(s) - humanities , physics , philosophy
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.