Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/9264| Título: | Problemas candidatos a np-intermediários e o problema de minimização de circuitos |
| Título(s) alternativo(s): | Np-intermediate candidate problems and the minimum circuit size problem |
| Autor(es): | Sdroievski, Nicollas Mocelin |
| Orientador(es): | Silva, Murilo Vicente Gonçalves da |
| Palavras-chave: | Complexidade computacional Oráculos Logarítmos Algorítmos Computational complexity Oracles Logarithms Algorithms |
| Data do documento: | 1-Jul-2016 |
| Editor: | Universidade Tecnológica Federal do Paraná |
| Câmpus: | Curitiba |
| Citação: | 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. |
| Resumo: | 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. |
| Abstract: | 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. |
| URI: | http://repositorio.utfpr.edu.br/jspui/handle/1/9264 |
| Aparece nas coleções: | CT - Sistemas de Informação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| CT_COSIS_2016_6.pdf | 682,59 kB | Adobe PDF |  Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.