Los invitamos a la presentación de Trabajo Final de Ignacio Made, hoy lunes a las 18hs en el Aula Magna de FaMAF.
Título: De PH a IP, un curso en Complejidad Computacional.
Autor: Ignacio Made.
Director: Miguel Campercholi.
Resumen: La teoría de la Complejidad Computacional es un campo relativamente nuevo que tiene un sinfín de problemas abiertos interesantes, cuyas soluciones tienen el potencial de impactar de manera directa en muchas disciplinas distintas. ¿Puede la computación cuántica resolver eficientemente problemas que la computación clásica no? ¿Puede el azar darle más poder a los algoritmos? ¿Encontrar una demostración es más difícil que verificarla? Son algunas preguntas que esta teoría intenta responder. En este trabajo se toma un segundo curso en Complejidad Computacional y se estudian algunas de las clases de complejidad más importantes junto a otros tópicos más avanzados. Se estudia la clase PH de la Jerarquía Polinomial, la clase de Circuitos Booleanos, la clase BPP de Computación Randomizada y la clase IP de Protocolos Interactivos. También se repasan las tres principales técnicas que tiene la teoría para encontrar resultados las cuales son Diagonalización, Lower Bounds y Aritmetización. Y además se ven sus respectivas “barreras” las cuales son Diagonalización, Natural Proofs y Algrebrización. Estas barreras son resultados que sugieren que para resolver los grandes problemas del campo, como el problema del milenio P vs NP, se van a necesitar nuevas ideas.
(source)