In this thesis, we study the discrete logarithm problem in the context of TFNP - the complexity class of search problems with a syntactically guaranteed existence of a solution for all instances. Our main results show that suitable variants of the discrete logarithm problem, which we call Index and DLog, are complete for the classes PPP and PWPP, respectively. Additionally, our reductions provide new structural insights into PWPP by establishing two new PWPP-complete problems. First, the problem Dove, a relaxation of the PPP-complete problem Pigeon. Dove is the first PWPP-complete problem not defined in terms of an explicitly shrinking function. Second, the problem Claw, a total search problem capturing the computational complexity of breaking claw-free permuta- tions. In the context of TFNP, the PWPP-completeness of Claw matches the known intrinsic relationship between collision-resistant hash functions and claw-free permuta- tions established in the cryptographic literature. 1

Title: NP search problems Author: Tomáš Jirotka Department: Department of Algebra Supervisor: Prof. RNDr. Jan Krajíček, DrSc. Abstract: The thesis summarizes known results in the field of NP search pro- blems. We discuss the complexity of integer factoring in detail, and we propose new results which place the problem in known classes and aim to separate it from PLS in some sense. Furthermore, we define several new search problems. Keywords: Computational complexity, TFNP, integer factorization. 1

Submitted by Bruno Donna de Mendonça (bruno.mendonca@yahoo.com.br) on 2017-06-29T00:11:11Z No. of bitstreams: 1 Dissertação - Bruno Mendonça - Registrada SRA.pdf: 1392496 bytes, checksum: 11544955ae98b00b7cf0fd4d100677c1 (MD5) / Approved for entry into archive by GILSON ROCHA MIRANDA (gilson.miranda@fgv.br) on 2017-06-30T13:47:41Z (GMT) No. of bitstreams: 1 Dissertação - Bruno Mendonça - Registrada SRA.pdf: 1392496 bytes, checksum: 11544955ae98b00b7cf0fd4d100677c1 (MD5) / Made available in DSpace on 2017-07-05T17:59:45Z (GMT). No. of bitstreams: 1 Dissertação - Bruno Mendonça - Registrada SRA.pdf: 1392496 bytes, checksum: 11544955ae98b00b7cf0fd4d100677c1 (MD5) Previous issue date: 2017-03-31 / Desde a crise de 2008 temos visto um fenômeno em que grande parte das economias desenvolvidas tem mantido taxas de juros bem próximas ao limite inferior durante períodos prolongados, Japão há mais de duas décadas e Estados Unidos e Europa por vários anos. Mesmo assim, com essas taxas de juros baixas a inflação nesses países tem permanecido em patamares baixos e ainda com menor volatilidade. No lado oposto do espectro, desde a adoção do Sistema de Metas de Inflação há quase 20 anos, o Brasil convive com as maiores taxas de juros reais do mundo por uma ampla vantagem. Apesar dessas características a economia brasileira conviveu com níveis elevados de inflação por todo o período, além de possuir uma grande tendência de aceleração no aumento do nível de preços ao menor sinal de algum desequilíbrio macroeconômico. A presente dissertação busca analisar essa característica da economia brasileira utilizando como framework a Teoria Fiscal do Nível de Preços. Para isso buscamos estudar o efeito que a composição da dívida pública federal brasileira pode ter sobre o controle da inflação através do mecanismo da taxa de juros utilizando um modelo de TFNP. De acordo com a teoria mencionada, chegaremos aos resultados que demonstram que manter grande parcela da dívida em títulos pós-fixados e outra em títulos indexados torna mais custoso o combate da inflação através dos juros e pode ter consequências no longo prazo.