[pt] Este trabalho é uma elaboração, com exemplos, e evolução do Algoritmo de Compressão Horizontal (HC) apresentado e seu Conjunto de Regras de Compressão. Este trabalho apresenta uma prova, feita no Provador Interativo de Teoremas Lean, de que o algoritmo HC pode obter uma Derivação Comprimida, representada por um Grafo Acíclico Dirigido, a partir de qualquer Derivação Tipo-Árvore em Dedução Natural para a Lógica Minimal Puramente Implicacional. Finalmente, a partir da Cobertura e Corretude do algoritmo HC, pode-se argumentar que NP = PSPACE. / [en] This work is an elaboration, with examples, and evolution of the presented Horizontal Compression Algorithm (HC) and its set of Compression Rules. This work argues a proof, done in the Lean Interactive Theorem Prover, that the HC algorithm can obtain a Compressed Derivation, represented by a Directed Acyclic Graph, from any Tree-Like Natural Deduction Derivation in Minimal Purely Implicational Logic. Finally, from the Coverage and Soundness of the HC algorithm, one can argue that NP = PSPACE.

Made available in DSpace on 2014-12-17T15:26:35Z (GMT). No. of bitstreams: 1 IsaacDBS.pdf: 539336 bytes, checksum: ac9f1f2543159f0c009f0242077b1d5c (MD5) Previous issue date: 2008-07-25 / In this work, we study and compare two percolation algorithms, one of then elaborated by Elias, and the other one by Newman and Ziff, using theorical tools of algorithms complexity and another algorithm that makes an experimental comparation. This work is divided in three chapters. The first one approaches some necessary definitions and theorems to a more formal mathematical study of percolation. The second presents technics that were used for the estimative calculation of the algorithms complexity, are they: worse case, better case e average case. We use the technique of the worse case to estimate the complexity of both algorithms and thus we can compare them. The last chapter shows several characteristics of each one of the algorithms and through the theoretical estimate of the complexity and the comparison between the execution time of the most important part of each one, we can compare these important algorithms that simulate the percolation. / Nesta disserta??o estudamos e comparamos dois algoritmos de percola??o, um elaborado por Elias e o outro por Newman e Ziff, utilizando ferramentas te?ricas da complexidade de algoritmos e um algoritmo que efetuou uma compara??o experimental. Dividimos este trabalho em tr?s cap?tulos. O primeiro aborda algumas defini??es e teoremas necess?rios a um estudo matem?tico mais formal da percola??o. O segundo apresenta t?cnicas utilizadas para o c?lculo estimativo de complexidade de algoritmos, sejam elas: pior caso, melhor caso e caso m?dio. Utilizamos a t?cnica do pior caso para estimar a complexidade de ambos algoritmos e assim podermos compar?-los. O ?ltimo cap?tulo mostra diversas caracter?sticas de cada um dos algoritmos e atrav?s da estima- tiva te?rica da complexidade e da compara??o entre os tempos de execu??o da parte mais importante de cada um, conseguimos comparar esses importantes algoritmos que simulam a percola??o