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

• Nicollas M. Sdroievski UTFPR
• Murilo V. G. da Silva UTFPR

DOI: https://doi.org/10.5753/etc.2016.9842

Resumo

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.

 

Referências

Allender, E., Buhrman, H., Kouck´y, M., van Melkebeek, D., and Ronneburger, D. (2006). Power from random strings. SIAM Journal on Computing, 35(6):1467–1493.

Allender, E. and Das, B. (2014). Zero knowledge and circuit minimization. Electronic Colloquium on Computational Complexity (ECCC), 21:68.

Arora, S. and Barak, B. (2009). Computational Complexity: A Modern Approach. Cambridge University Press, New York, NY, USA, 1st edition.

Goldwasser, S., Micali, S., and Rackoff, C. (1989). The knowledge complexity of interactive proof systems. SIAM J. Comput., 18(1):186–208.

Hirahara, S. and Watanabe, O. (2015). Limits of minimum circuit size problem as oracle. Electronic Colloquium on Computational Complexity (ECCC), 22:198.

H¨astad, J., Impagliazzo, R., Levin, L. A., and Luby, M. (1999). A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28(4):1364–1396.

Ladner, R. E. (1975). On the structure of polynomial time reducibility. J. ACM, 22(1):155–171.

Malka, L. (2008). A Study of Perfect Zero-knowledge Proofs. PhD thesis, Victoria, B.C., Canada, Canada.