De PH a IP : un curso en complejidad computacional

Mostrar todas las versiones(2)

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.

Guardado en:

Detalles Bibliográficos
Autor principal:	Made Vollenweider, Ignacio
Otros Autores:	Campercholi, Miguel Alejandro Carlos
Formato:	bachelorThesis
Lenguaje:	Español
Publicado:	2020
Materias:	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
Acceso en línea:	http://hdl.handle.net/11086/16009
Aporte de:	Repositorio Digital Universitario (UNC) de Universidad Nacional de Córdoba

id	I10-R141-11086-16009
record_format	dspace
spelling	I10-R141-11086-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/
institution	Universidad Nacional de Córdoba
institution_str	I-10
repository_str	R-141
collection	Repositorio Digital Universitario (UNC)
language	Español
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
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
topic_facet	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
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.
author2	Campercholi, Miguel Alejandro Carlos
author_facet	Campercholi, Miguel Alejandro Carlos Made Vollenweider, Ignacio
format	bachelorThesis
author	Made Vollenweider, Ignacio
author_sort	Made Vollenweider, Ignacio
title	De PH a IP : un curso en complejidad computacional
title_short	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_sort	de ph a ip : un curso en complejidad computacional
publishDate	2020
url	http://hdl.handle.net/11086/16009
work_keys_str_mv	AT madevollenweiderignacio dephaipuncursoencomplejidadcomputacional
_version_	1782014871270850560

De PH a IP : un curso en complejidad computacional

Ejemplares similares