1. Repositório Institucional da Universidade Tecnológica Federal do Paraná (RIUT)
  2. GRAD - Cursos de Graduação
  3. TCC - Trabalhos de Conclusão de Curso de Graduação
  4. Curitiba
  5. CT - Sistemas de Informação
Use este identificador para citar ou linkar para este item: http://repositorio.utfpr.edu.br/jspui/handle/1/9264
Registro completo de metadados
Campo DCValorIdioma
dc.creatorSdroievski, Nicollas Mocelin
dc.date.accessioned2020-11-12T12:03:02Z-
dc.date.available2020-11-12T12:03:02Z-
dc.date.issued2016-07-01
dc.identifier.citationSDROIEVSKI, 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.pt_BR
dc.identifier.urihttp://repositorio.utfpr.edu.br/jspui/handle/1/9264-
dc.description.abstractIn 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.pt_BR
dc.languageporpt_BR
dc.publisherUniversidade Tecnológica Federal do Paranápt_BR
dc.rightsopenAccesspt_BR
dc.subjectComplexidade computacionalpt_BR
dc.subjectOráculospt_BR
dc.subjectLogarítmospt_BR
dc.subjectAlgorítmospt_BR
dc.subjectComputational complexity pt_BR
dc.subjectOraclespt_BR
dc.subjectLogarithmspt_BR
dc.subjectAlgorithmspt_BR
dc.titleProblemas candidatos a np-intermediários e o problema de minimização de circuitospt_BR
dc.title.alternativeNp-intermediate candidate problems and the minimum circuit size problempt_BR
dc.typebachelorThesispt_BR
dc.description.resumoNeste 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.pt_BR
dc.degree.localCuritibapt_BR
dc.publisher.localCuritibapt_BR
dc.contributor.advisor1Silva, Murilo Vicente Gonçalves da
dc.contributor.referee1Silva, Murilo Vicente Gonçalves da
dc.contributor.referee2Silva, Murilo Vicente Gonçalves da
dc.contributor.referee3Silva, Murilo Vicente Gonçalves da
dc.publisher.countryBrasilpt_BR
dc.publisher.programBacharelado em Sistemas de Informaçãopt_BR
dc.publisher.initialsUTFPRpt_BR
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::ANALISE DE ALGORITMOS E COMPLEXIDADE DE COMPUTACAOpt_BR
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 PDFThumbnail
Visualizar/Abrir
Mostrar registro simples do item Recomendar este item Visualizar estatísticas


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