Conhecimento Zero Estatístico e Reduções Eficientes para o Problema MKTP
Resumo
Este artigo e um resumo da dissertação de mestrado de mesmo título, na qual estudamos a complexidade de problemas computacionais candidatos a NP-intermediários. Nesse processo, conectamos a classe SZK, relacionada a provas de conhecimento zero, com o problema computacional MKTP, relacionado a teoria algorítmica da informação. Como contribuições originais, destacamos reduções aleatorizadas do PROBLEMA DO SUBGRUPO OCULTO (HSP) e outros problemas em teoria computacional de grupos para MKTP, e provas de conhecimento zero estat´ıstico para versões de decisão do problema HSP.
Palavras-chave:
Complexidade Computacional, NP-intermediário, Provas de Conhecimento Zero, MKTP, Redução Aleatorizada, Problema do Subgrupo Oculto, Equivalência de Grupos.
Referências
Allender, E., Buhrman, H., Kouck´y, M., van Melkebeek, D., and Ronneburger, D. (2006). Power from random strings. SIAM Journal on Computing, 35(6):1467–1493.
Allender, E., Grochow, J. A., van Melkebeek, D., Moore, C., and Morgan, A. (2018). Minimum Circuit Size, Graph Isomorphism, and Related Problems. In Karlin, A. R., editor, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), vo- lume 94 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1– 20:20, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
Arora, S. and Barak, B. (2009). Computational Complexity: A Modern Approach. Cam- bridge University Press, New York, NY, USA, 1st edition.
Arvind, V. and Das, B. (2008). Szk proofs for black-box group problems. Theory of Computing Systems, 43(2):100–117.
Babai, L. and Beals, R. (1998). A Polynomial-time Theory of Black-box Groups I (ma- nuscrito).
Boppana, R. B., Hastad, J., and Zachos, S. (1987). Does co-np have short interactive proofs? Inf. Process. Lett., 25(2):127–132.
Fenner, S. A. and Zhang, Y. (2005). Quantum algorithms for a set of group theoretic problems. In Coppo, M., Lodi, E., and Pinna, G. M., editors, Theoretical Computer Science, pages 215–227, Berlin, Heidelberg. Springer Berlin Heidelberg.
Goldwasser, S., Micali, S., and Rackoff, C. (1989). The knowledge complexity of inte- ractive proof systems. SIAM J. Comput., 18(1):186–208.
Hirahara, S. and Watanabe, O. (2015). Limits of minimum circuit size problem as oracle. Electronic Colloquium on Computational Complexity (ECCC), 22:198.
Ladner, R. E. (1975). On the structure of polynomial time reducibility. J. ACM, 22(1):155–171.
Li, M. and Vit´anyi, P. (1997). An introduction to Kolmogorov complexity and its applica- tions. Springer-Verlag, 2 edition.
Murray, C. and Williams, R. (2014). On the (non) np-hardness of computing circuit complexity. Electronic Colloquium on Computational Complexity (ECCC), 21:164.
Sdroievski, N. M. (2018). Conhecimento Zero Estatıstico e Reducoes Eficientes para o Problema MKTP. Dissertacao de mestrado, Departamento de Informatica, Universidade Federal do Parana (UFPR).
Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput., 26(5):1484–1509.
Vadhan, S. P. (1999). A Study of Statistical Zero-knowledge Proofs. PhD thesis, Massa- chusetts Institute of Technology, Cambridge, MA, USA. AAI0801528.
Allender, E., Grochow, J. A., van Melkebeek, D., Moore, C., and Morgan, A. (2018). Minimum Circuit Size, Graph Isomorphism, and Related Problems. In Karlin, A. R., editor, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), vo- lume 94 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1– 20:20, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
Arora, S. and Barak, B. (2009). Computational Complexity: A Modern Approach. Cam- bridge University Press, New York, NY, USA, 1st edition.
Arvind, V. and Das, B. (2008). Szk proofs for black-box group problems. Theory of Computing Systems, 43(2):100–117.
Babai, L. and Beals, R. (1998). A Polynomial-time Theory of Black-box Groups I (ma- nuscrito).
Boppana, R. B., Hastad, J., and Zachos, S. (1987). Does co-np have short interactive proofs? Inf. Process. Lett., 25(2):127–132.
Fenner, S. A. and Zhang, Y. (2005). Quantum algorithms for a set of group theoretic problems. In Coppo, M., Lodi, E., and Pinna, G. M., editors, Theoretical Computer Science, pages 215–227, Berlin, Heidelberg. Springer Berlin Heidelberg.
Goldwasser, S., Micali, S., and Rackoff, C. (1989). The knowledge complexity of inte- ractive proof systems. SIAM J. Comput., 18(1):186–208.
Hirahara, S. and Watanabe, O. (2015). Limits of minimum circuit size problem as oracle. Electronic Colloquium on Computational Complexity (ECCC), 22:198.
Ladner, R. E. (1975). On the structure of polynomial time reducibility. J. ACM, 22(1):155–171.
Li, M. and Vit´anyi, P. (1997). An introduction to Kolmogorov complexity and its applica- tions. Springer-Verlag, 2 edition.
Murray, C. and Williams, R. (2014). On the (non) np-hardness of computing circuit complexity. Electronic Colloquium on Computational Complexity (ECCC), 21:164.
Sdroievski, N. M. (2018). Conhecimento Zero Estatıstico e Reducoes Eficientes para o Problema MKTP. Dissertacao de mestrado, Departamento de Informatica, Universidade Federal do Parana (UFPR).
Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput., 26(5):1484–1509.
Vadhan, S. P. (1999). A Study of Statistical Zero-knowledge Proofs. PhD thesis, Massa- chusetts Institute of Technology, Cambridge, MA, USA. AAI0801528.
Publicado
26/06/2019
Como Citar
SDROIEVSKI, Nicollas M.; DA SILVA, Murilo V. G.; VIGNATTI, André L..
Conhecimento Zero Estatístico e Reduções Eficientes para o Problema MKTP. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 32. , 2019, Belém.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
ISSN 2763-8820.
DOI: https://doi.org/10.5753/ctd.2019.6336.
