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

Abstract

Resumo: 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.

Abstract: 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.