Conhecimento zero estatístico e reduções eficientes para o problema MKTP

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorSilva, Murilo Vicente Gonçalves da-
Autor(es): dc.contributorVignatti, André Luís-
Autor(es): dc.contributorUniversidade Federal do Paraná. Setor de Ciências Exatas. Programa de Pós-Graduação em Informática-
Autor(es): dc.creatorSdroievski, Nicollas Mocelin-
Data de aceite: dc.date.accessioned2019-08-21T23:29:20Z-
Data de disponibilização: dc.date.available2019-08-21T23:29:20Z-
Data de envio: dc.date.issued2019-03-07-
Data de envio: dc.date.issued2019-03-07-
Data de envio: dc.date.issued2018-
Fonte completa do material: dc.identifierhttps://hdl.handle.net/1884/58601-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/1884/58601-
Descrição: dc.descriptionOrientador: Murilo Vicente Gonçalves da Silva-
Descrição: dc.descriptionCoorientador: André Luís Vignatti-
Descrição: dc.descriptionDissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa : Curitiba, 04/12/2018-
Descrição: dc.descriptionInclui referências: p.133-136-
Descrição: dc.descriptionÁrea de concentração: Ciência da Computação-
Descrição: dc.descriptionResumo: Nesta dissertação, estudamos a complexidade computacional de vários problemas candidatos a NP-intermediários. Mais precisamente, estudamos a relação destes problemas com a classe de complexidade SZK, a classe dos problemas que admitem provas de conhecimento zero estatístico e suas subclasses. Além disso, estudamos reduções destes problemas para o problema também candidato a NP-intermediário MKTP, relacionado a uma versão limitada em tempo de complexidade de Kolmogorov denominada KT. Além de realizar um levantamento de literatura, aplicamos as técnicas estudadas para obter resultados originais. Dentre esses destacamos uma redução aleatorizada do Problema do Subgrupo Oculto para MKTP, provas de conhecimento zero para duas versões de decisão do Problema do Subgrupo Oculto, reduções aleatorizadas dos problemas de Equivalência de Grupos e Equivalência de Grupos Simétricos para MKTP e uma indexação para resíduos quadráticos que é decodificável por circuitos de tamanho polinomial. Palavras-chave: Complexidade Computacional, NP-intermediário, Provas de Conhecimento Zero, MKTP, Redução Aleatorizada, Problema do Subgrupo Oculto, Equivalência de Grupos, Indexação Eficientemente Decodificável.-
Descrição: dc.descriptionAbstract: In this dissertation, we study the computational complexity of various NP-intermediate candidate problems. More precisely, we study these problem's relations to the complexity class SZK, the class of problems that admit statistical zero knowledge proofs, and its subclasses. We also study reductions from these problems to the NP-intermediate candidate problem MKTP, which is related to a time-bounded version of Kolmogorov complexity named KT. Besides doing literature review, we apply the studied techniques to obtain original results. Of these we highlight a randomized reduction from the Hidden Subgroup Problem to MKTP, zero knowledge proofs for two decision versions of the Hidden Subgroup Problem, randomized reductions from the Group Equivalence and Permutation Group Equivalence problems to MKTP and an indexing for quadratic residues that is decodable by polynomial size circuits. Keywords: Computational Complexity, NP-intermediate, Zero Knowledge Proofs, MKTP, Randomized Reduction, Hidden Subgroup Problem, Group Equivalence, Efficiently Decodable Indexing.-
Formato: dc.format146 p. : il.-
Formato: dc.formatapplication/pdf-
Formato: dc.formatapplication/pdf-
Palavras-chave: dc.subjectPolinomios-
Palavras-chave: dc.subjectCiência da Computação-
Palavras-chave: dc.subjectProbabilidades-
Palavras-chave: dc.subjectSistemas de computação interativos-
Palavras-chave: dc.subjectTeses-
Título: dc.titleConhecimento zero estatístico e reduções eficientes para o problema MKTP-
Aparece nas coleções:Repositório Institucional - Rede Paraná Acervo

Não existem arquivos associados a este item.