De PH a IP : un curso en complejidad computacional
Tesis (Lic. en Cs. de la Computación)--Universidad Nacional de Córdoba, Facultad de Matemática, Astronomía, Física y Computación, 2019.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | bachelorThesis |
| Language: | spa |
| Published: |
2020
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/11086/16009 |
| _version_ | 1801215683137110016 |
|---|---|
| author | Made Vollenweider, Ignacio |
| author2 | Campercholi, Miguel Alejandro Carlos |
| author_facet | Campercholi, Miguel Alejandro Carlos Made Vollenweider, Ignacio |
| author_sort | Made Vollenweider, Ignacio |
| collection | Repositorio Digital Universitario |
| description | Tesis (Lic. en Cs. de la Computación)--Universidad Nacional de Córdoba, Facultad de Matemática, Astronomía, Física y Computación, 2019. |
| format | bachelorThesis |
| id | rdu-unc.16009 |
| institution | Universidad Nacional de Cordoba |
| language | spa |
| publishDate | 2020 |
| record_format | dspace |
| spelling | rdu-unc.160092023-08-31T13:19:21Z De PH a IP : un curso en complejidad computacional Made Vollenweider, Ignacio Campercholi, Miguel Alejandro Carlos Máquina de Turing Clase de complejidad Lenguaje en computación Polinomial P vs NP SAT Turing machine Complexity classes Polynomial Theory of computation Computational complexity and cryptography Complexity classes; Problems, Reductions and completeness; Circuit complexity, Interactive proof systems Tesis (Lic. en Cs. de la Computación)--Universidad Nacional de Córdoba, Facultad de Matemática, Astronomía, Física y Computación, 2019. Fil: Made Vollenweider, Ignacio. Universidad Nacional de Córdoba. Facultad de Matemática, Astronomía, Física y Computación; Argentina. En este trabajo estudiamos algunas de las clases más importantes de la teoría de Complejidad Computacional. Nos basamos en el programa que propone el libro Computational Complexity a modern approach, del cual vemos la segunda mitad de la primera parte del programa (excluyendo Criptografía, Computación Cuántica y el Teorema PCP). En particular, estudiamos la clase de la Jerarquía Polinomial (PH), la clase de Circuitos Booleanos (P /poly ), la Computación Randomizada (BPP) y los Protocolos Interactivos (IP). Además vemos las principales técnicas de la teoría para obtener resultados las cuales son Diagonalización, Lower bounds y Arithmetization. Y estudiamos también sus respectivas limitaciones: Relativización, Natural proofs y Algebrization. In this work we study some of the most important classes of the Computational Complexity Theory. We base on the program proposed by the book Computational Complexity a modern approach, of which we see the second half of the first part of the program (excluding Cryptography, Quantum Computing and the PCP Theorem). In particular, we study the class of the Polynomial Hierarchy (PH), the class of Boolean Circuits (P /poly ), the Randomized Computing (BPP) and the Interactive Protocols (IP). In addition we see the main techniques of the theory to obtain results which are Diagonalization, Lower bounds and Arithmetization. And we also study their respective limitations: Relativization, Natural proofs and Algebrization. Fil: Made Vollenweider, Ignacio. Universidad Nacional de Córdoba. Facultad de Matemática, Astronomía, Física y Computación; Argentina. 2020-08-26T17:17:33Z 2020-08-26T17:17:33Z 2019-11 bachelorThesis http://hdl.handle.net/11086/16009 spa Atribución 4.0 Internacional http://creativecommons.org/licenses/by/4.0/ |
| spellingShingle | Máquina de Turing Clase de complejidad Lenguaje en computación Polinomial P vs NP SAT Turing machine Complexity classes Polynomial Theory of computation Computational complexity and cryptography Complexity classes; Problems, Reductions and completeness; Circuit complexity, Interactive proof systems Made Vollenweider, Ignacio De PH a IP : un curso en complejidad computacional |
| title | De PH a IP : un curso en complejidad computacional |
| title_full | De PH a IP : un curso en complejidad computacional |
| title_fullStr | De PH a IP : un curso en complejidad computacional |
| title_full_unstemmed | De PH a IP : un curso en complejidad computacional |
| title_short | De PH a IP : un curso en complejidad computacional |
| title_sort | de ph a ip un curso en complejidad computacional |
| topic | Máquina de Turing Clase de complejidad Lenguaje en computación Polinomial P vs NP SAT Turing machine Complexity classes Polynomial Theory of computation Computational complexity and cryptography Complexity classes; Problems, Reductions and completeness; Circuit complexity, Interactive proof systems |
| url | http://hdl.handle.net/11086/16009 |
| work_keys_str_mv | AT madevollenweiderignacio dephaipuncursoencomplejidadcomputacional |