Problemas candidatos a np-intermediários e o problema de minimização de circuitos
In this work we study the state of the art of Computational Complexity, focusing on classes defined around discrete probability concepts. More specifically we study four problems that are NP-intermediate candidates, the minimum circuit size problem, graph isomorphism, quadratic residue and discrete...
| Autor principal: | Sdroievski, Nicollas Mocelin |
|---|---|
| Formato: | Trabalho de Conclusão de Curso (Graduação) |
| Idioma: | Português |
| Publicado em: |
Universidade Tecnológica Federal do Paraná
2020
|
| Assuntos: | |
| Acesso em linha: |
http://repositorio.utfpr.edu.br/jspui/handle/1/9264 |
| Tags: |
Adicionar Tag
Sem tags, seja o primeiro a adicionar uma tag!
|
| Resumo: |
In this work we study the state of the art of Computational Complexity, focusing on classes defined around discrete probability concepts. More specifically we study four problems that are NP-intermediate candidates, the minimum circuit size problem, graph isomorphism, quadratic residue and discrete logarithm. We also expose the power that an oracle for the minimum circuit size problem possesses, and show explicitly two randomized polynomial time algorithms with oracle access to the minimum circuit size problem, whose existence was only indirectly known. The first algorithm solves the quadratic residue problem and the second one solves the discrete logarithm problem. |
|---|