Use este identificador para citar ou linkar para este item: http://repositorio.roca.utfpr.edu.br/jspui/handle/1/8241
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
Referência: 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.roca.utfpr.edu.br/jspui/handle/1/8241
Aparece nas coleções:CT - Sistemas de Informação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
CT_COSIS_2016_6.pdf682,59 kBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.