Saber UCV
Repositorio Institucional
Repositorio Institucional
Please use this identifier to cite or link to this item:
https://saber.ucv.ve/handle/10872/17714
|
| Title: | Completitud en el segundo nivel de la jerarquía polinomial a través de propiedades sintácticas |
| Authors: | Pin Baque, Edwin |
| Keywords: | Teorema de Fagin Complejidad Descriptiva |
| Issue Date: | 5-Feb-2018 |
| Abstract: | Resumen La Teoría de Complejidad Descriptiva se basa en la caracterización de clases de complejidad,problemas de decisión, reducciones y demás conceptos computacionales a través de sistemas linguísticos formales como la lógica de primer orden, la lógica de segundo orden, entre otros. El resultado que dio inicio a este tipo de investigaciones se conoce como Teorema de Fagin y plantea que la clase de complejidad NP es el conjunto de problemas expresables mediante fórmulas de segundo orden existenciales. Stockmeyer generalizó este resultado al defi nir inductivamente nuevas clases de complejidad, denotadas por pk, capturadas por fragmentos más generales de fórmulas de segundo orden y cuya unión da como resultado la clase de todos los problemas expresables en segundo orden. Esta última clase, denominada Jerarquía Polinomial, ha sido bastante estudiada desde su formulación. En este trabajo nos concentramos en el segundo nivel de la Jerarquía Polinomial, la clase de complejidad p2. Uno de los puntos más importantes que se estudian dada una clase de complejidad C es la propiedad de completitud. Un problema A se dice que es C-completo si cualquier otro problema en C se puede interpretar y resolver efi cientemente a través de A. Desde que Stephen Cook demostrara en 1971 la existencia de problemas NP-completos, la cantidad de resultados obtenidos bajo este concepto han sido abrumadores. Desde la perspectiva de la Complejidad Descriptiva, un problema B se puede reducir a un problema A efi cientemente, si existe una interpretación de B en A descrita mediante fórmulas de primer orden. En este ámbito, Immerman y Landau demostraron varias propiedades de un tipo especial de reducciones, denominadas como proyecciones. Si bien las proyecciones caracterizan la completitud en un sentido más restrictivo que cualquier otro tipo de reducción, la mayoría de los problemas naturales que se han demostrado completos en sus respectivas clases de complejidad también se muestran completos bajo este tipo de reducciones. Medina e Immerman demostraron que la clase de problemas NP-completos vía proyecciones también se puede caracterizar sintácticamente, en el mismo sentido que establece el Teorema de Fagin, es decir,existe un fragmento de fórmulas de segundo orden que caracteriza a la clase de problemas NP-completos vía proyecciones. Este resultado fue generalizado por Borges y Bonet en el a~no 2008 para cualquier clase de complejidad C con ciertas características especiales. En ese mismo trabajo proporcionarán métodos de carácter sintáctico y combinatorio para demostrar la completitud de una extensa lista de problemas. Uno de tales métodos se denominó superfluidad. La técnica de superfluidad se basa en el estudio de conjunciones de la forma (' ^ ),donde es una sentencia universal de primer orden y es una fórmula sobre una lógica L que captura a una clase de complejidad C. Si L y C satisfacen ciertas propiedades, entonces la C-completitud del problema asociado a la fórmula (' ^ ) implica la C-completitud del problema asociado a . Esta propiedad se estudió y se demostró válida por primera vez en las clases de complejidad NL, P, NP y coNP. Siguiendo esa línea de investigación, en esta monografía se realiza un estudio exhaustivo de la clase de complejidad p 2 , con el propósito de obtener la propiedad de superfluidad, la cual se ha probado válida tanto en esta clase como en su complemento. Se proporciona además una lista de problemas clasifi cados como p 2-completos vía proyecciones. |
| Description: | Pin Baque, Edwin (2016) Completitud en el segundo nivel de la jerarquía polinomial a través de propiedades sintácticas. Trabajo de Grado presentado ante la Universidad Central de Venezuela para optar por el Título de Magister Scientiarium, Mención Matemática |
| URI: | http://hdl.handle.net/10872/17714 |
| Appears in Collections: | Maestría |
Files in This Item:
|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.