Atenção: Todas as denúncias são sigilosas e sua identidade será preservada.
Os campos nome e e-mail são de preenchimento opcional
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Silva, Murilo Vicente Gonçalves da | - |
Autor(es): dc.contributor | Silva, Murilo Vicente Gonçalves da | - |
Autor(es): dc.contributor | Silva, Murilo Vicente Gonçalves da | - |
Autor(es): dc.contributor | Silva, Murilo Vicente Gonçalves da | - |
Autor(es): dc.creator | Sdroievski, Nicollas Mocelin | - |
Data de aceite: dc.date.accessioned | 2022-02-21T21:49:29Z | - |
Data de disponibilização: dc.date.available | 2022-02-21T21:49:29Z | - |
Data de envio: dc.date.issued | 2020-11-11 | - |
Data de envio: dc.date.issued | 2020-11-11 | - |
Data de envio: dc.date.issued | 2016-07-01 | - |
Fonte completa do material: dc.identifier | http://repositorio.utfpr.edu.br/jspui/handle/1/9264 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/661377 | - |
Descrição: dc.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. | - |
Descrição: dc.description | 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. | - |
Formato: dc.format | application/pdf | - |
Idioma: dc.language | pt_BR | - |
Publicador: dc.publisher | Universidade Tecnológica Federal do Paraná | - |
Publicador: dc.publisher | Curitiba | - |
Publicador: dc.publisher | Brasil | - |
Publicador: dc.publisher | Bacharelado em Sistemas de Informação | - |
Publicador: dc.publisher | UTFPR | - |
Direitos: dc.rights | openAccess | - |
Palavras-chave: dc.subject | Complexidade computacional | - |
Palavras-chave: dc.subject | Oráculos | - |
Palavras-chave: dc.subject | Logarítmos | - |
Palavras-chave: dc.subject | Algorítmos | - |
Palavras-chave: dc.subject | Computational complexity | - |
Palavras-chave: dc.subject | Oracles | - |
Palavras-chave: dc.subject | Logarithms | - |
Palavras-chave: dc.subject | Algorithms | - |
Palavras-chave: dc.subject | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::ANALISE DE ALGORITMOS E COMPLEXIDADE DE COMPUTACAO | - |
Título: dc.title | Problemas candidatos a np-intermediários e o problema de minimização de circuitos | - |
Título: dc.title | Np-intermediate candidate problems and the minimum circuit size problem | - |
Tipo de arquivo: dc.type | livro digital | - |
Aparece nas coleções: | Repositorio Institucional da UTFPR - RIUT |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: