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!
|
| id |
riut-1-9264 |
|---|---|
| recordtype |
dspace |
| spelling |
riut-1-92642020-11-12T12:03:03Z Problemas candidatos a np-intermediários e o problema de minimização de circuitos Np-intermediate candidate problems and the minimum circuit size problem Sdroievski, Nicollas Mocelin Silva, Murilo Vicente Gonçalves da Silva, Murilo Vicente Gonçalves da Silva, Murilo Vicente Gonçalves da Silva, Murilo Vicente Gonçalves da Complexidade computacional Oráculos Logarítmos Algorítmos Computational complexity Oracles Logarithms Algorithms CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::ANALISE DE ALGORITMOS E COMPLEXIDADE DE COMPUTACAO 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. Neste trabalho é realizada fundamentação teórica do estado da arte da área de Complexidade Computacional, com foco para as classes definidas em torno de conceitos de probabilidade discreta. Mais especificamente s~ao estudados quatro problemas candidatos a NP-intermedários, os problemas de minimização de circuitos, isomorfismo de grafos, resíduo quadrático e logaritmo discreto. Por ´ultimo ´e exposto o poder de um oráculo para o poder de minimiza¸c~ao de circuitos, e s~ao mostrados explicitamente dois algoritmos aleatorizados polinomiais com oráculo para o problema de minimização de circuitos, cuja existência era conhecida apenas de forma indireta. O primeiro algoritmo resolve o problema do resíduo quadrático e o segundo o problema do logaritmo discreto. 2020-11-12T12:03:02Z 2020-11-12T12:03:02Z 2016-07-01 bachelorThesis SDROIEVSKI, Nicollas Mocelin. Problemas candidatos a np-intermediários e o problema de minimização de circuitos. 2016. 70 f. Trabalho de Conclusão de Curso (Bacharelado em Sistemas de Informação) - Universidade Tecnológica Federal do Paraná, Curitiba, 2016. http://repositorio.utfpr.edu.br/jspui/handle/1/9264 por openAccess application/pdf Universidade Tecnológica Federal do Paraná Curitiba Brasil Bacharelado em Sistemas de Informação UTFPR |
| institution |
Universidade Tecnológica Federal do Paraná |
| collection |
RIUT |
| language |
Português |
| topic |
Complexidade computacional Oráculos Logarítmos Algorítmos Computational complexity Oracles Logarithms Algorithms CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::ANALISE DE ALGORITMOS E COMPLEXIDADE DE COMPUTACAO |
| spellingShingle |
Complexidade computacional Oráculos Logarítmos Algorítmos Computational complexity Oracles Logarithms Algorithms CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::ANALISE DE ALGORITMOS E COMPLEXIDADE DE COMPUTACAO Sdroievski, Nicollas Mocelin Problemas candidatos a np-intermediários e o problema de minimização de circuitos |
| description |
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. |
| format |
Trabalho de Conclusão de Curso (Graduação) |
| author |
Sdroievski, Nicollas Mocelin |
| author_sort |
Sdroievski, Nicollas Mocelin |
| title |
Problemas candidatos a np-intermediários e o problema de minimização de circuitos |
| title_short |
Problemas candidatos a np-intermediários e o problema de minimização de circuitos |
| title_full |
Problemas candidatos a np-intermediários e o problema de minimização de circuitos |
| title_fullStr |
Problemas candidatos a np-intermediários e o problema de minimização de circuitos |
| title_full_unstemmed |
Problemas candidatos a np-intermediários e o problema de minimização de circuitos |
| title_sort |
problemas candidatos a np-intermediários e o problema de minimização de circuitos |
| publisher |
Universidade Tecnológica Federal do Paraná |
| publishDate |
2020 |
| citation |
SDROIEVSKI, Nicollas Mocelin. Problemas candidatos a np-intermediários e o problema de minimização de circuitos. 2016. 70 f. Trabalho de Conclusão de Curso (Bacharelado em Sistemas de Informação) - Universidade Tecnológica Federal do Paraná, Curitiba, 2016. |
| url |
http://repositorio.utfpr.edu.br/jspui/handle/1/9264 |
| _version_ |
1805309449909305344 |
| score |
10,814766 |