Problemas candidatos a np-intermediários e o problema de minimização de circuitos

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorSilva, Murilo Vicente Gonçalves da-
Autor(es): dc.contributorSilva, Murilo Vicente Gonçalves da-
Autor(es): dc.contributorSilva, Murilo Vicente Gonçalves da-
Autor(es): dc.contributorSilva, Murilo Vicente Gonçalves da-
Autor(es): dc.creatorSdroievski, Nicollas Mocelin-
Data de aceite: dc.date.accessioned2022-02-21T21:49:29Z-
Data de disponibilização: dc.date.available2022-02-21T21:49:29Z-
Data de envio: dc.date.issued2020-11-11-
Data de envio: dc.date.issued2020-11-11-
Data de envio: dc.date.issued2016-07-01-
Fonte completa do material: dc.identifierhttp://repositorio.utfpr.edu.br/jspui/handle/1/9264-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/661377-
Descrição: dc.descriptionIn 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.-
Descrição: dc.descriptionNeste 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.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Publicador: dc.publisherUniversidade Tecnológica Federal do Paraná-
Publicador: dc.publisherCuritiba-
Publicador: dc.publisherBrasil-
Publicador: dc.publisherBacharelado em Sistemas de Informação-
Publicador: dc.publisherUTFPR-
Direitos: dc.rightsopenAccess-
Palavras-chave: dc.subjectComplexidade computacional-
Palavras-chave: dc.subjectOráculos-
Palavras-chave: dc.subjectLogarítmos-
Palavras-chave: dc.subjectAlgorítmos-
Palavras-chave: dc.subjectComputational complexity -
Palavras-chave: dc.subjectOracles-
Palavras-chave: dc.subjectLogarithms-
Palavras-chave: dc.subjectAlgorithms-
Palavras-chave: dc.subjectCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::ANALISE DE ALGORITMOS E COMPLEXIDADE DE COMPUTACAO-
Título: dc.titleProblemas candidatos a np-intermediários e o problema de minimização de circuitos-
Título: dc.titleNp-intermediate candidate problems and the minimum circuit size problem-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositorio Institucional da UTFPR - RIUT

Não existem arquivos associados a este item.