Un modelo de cómputo basado en ocultamiento de la información para cotas inferiores de complejidad en geometría algebraica efectiva

Institución otorgante:

Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales

Fecha:

2018-02-26

Tipo de documento: 

info:eu-repo/semantics/doctoralThesis
 

Formato:

application/pdf

Idioma:

eng

Temas:

TIPO ABSTRACTO DE DATOS - FUNCION DE ABSTRACCION - ALGORITMO DE ELIMINACION - INTERPOLACION - OCULTAMIENTO DE LA INFORMACION - COTA INFERIOR DE COMPLEJIDAD - REQUERIMIENTO NO-FUNCIONAL - ROBUSTEZ - DIAGRAMA DE CLASES - MODELO DE COMPUTO - PROGRAMACION ORIENTADA A OBJETOS - POLINOMIOS - DISEÑO DE SOFTWARE - ABSTRACT DATA TYPE - ABSTRACTION FUNCTION - ELIMINATION ALGORITHM - INTERPOLATION - INFORMATION HIDING - LOWER COMPLEXITY BOUND - NON-FUNCTIONAL REQUIREMENT - ROBUSTNESS - CLASS DIAGRAM - COMPUTATION MODEL - OBJECT-ORIENTED PROGRAMMING - POLYNOMIALS - SOFTWARE DESIGN

Descripción:

Para estudiar la complejidad intrínseca de un problema computacionalsiempre es posible dar y demostrar cotas inferiores de complejidad. Unacota inferior de complejidad es un teorema que establece la mínima complejidad que tiene cualquier algoritmo que intente resolver el problema que estamos considerando. Con esta definición, una cota posible es (1) que es una cota inferior trivial, cualquier algoritmo tarda al menos un paso. Lodifícil es obtener una cota inferior alta. Cuanto más alta es la cota inferior, es más difícil de demostrar, por ejemplo, aún es una pregunta abierta saber si existen o no cotas inferiores exponenciales para problemas en la clase de complejidad NP. En esta tesis se establece que la dificultad de encontrar tales cotas puede deberse a la naturaleza del modelo de cómputoutilizado que no debe ser general ni muy específico. Esta idea empezó con la noción de algoritmo programable (programmable algorithm) que distingueentre algoritmos en general y algoritmos producidos siguiendo unaespecificación (ver [HKRP13b]). De acuerdo con [Bor75], obtener una cotainferior de complejidad requiere la definición de dos ingredientes fundamentales:el modelo de cómputo que contiene los algoritmos que vamos aestudiar y una adecuada medida de complejidad computacional. Entonces,vamos a ser cuidadosos con la definición de estos ingredientes y vamos adefinir un modelo de cómputo para algoritmos programables en el sentidode [HKRP13b]. En particular, en esta tesis introducimos un modelo decómputo basado en conceptos de Ingeniería de Software. Esta característicapermite demostrar cotas inferiores de complejidad no triviales paraalgoritmos de eliminación en geometría algebraica efectiva. Esta tesis esta basada en un proyecto de 20 años de investigación encomplejidad algebraica y teoría del cálculo simbólico que fue iniciado en eltrabajo J. Heintz, J. Morgenstern, On the Intrinsic Complexity of Elimination Theory, Journal of Complexity 9 471-498 (1993). El objetivo originaldel proyecto fue determinar la complejidad intrínseca de resolver sistemasde ecuaciones polinomiales (teoría de la eliminación), se quería demostrar sucarácter de complejidad no polinomial. Este objetivo fue logrado en esenciaen el trabajo J. Heintz, B. Kuijpers, A. Rojas Paredes, Software Engineeringand Complexity in Effective Algebraic Geometry, Journal of Complexity 29 92-138 (2013), Journal of Complexity 2013 Best Paper Award, dondese fijó la estructura de datos que utilizaban los algoritmos de eliminación,esto se llamó modelo de circuitos (polinomios implementados en términosde circuitos aritméticos). Más tarde nos dimos cuenta de que el modelo de circuitos no era esencialy que nuestra argumentación también podía aplicarse a otras cuestiones decomplejidad en el cálculo científico, por ejemplo, la interpolación polinomial (ver [GHMS11]). La observación principal fue que habíamos desarrollado en nuestro contexto un modelo matemático para ciertos aspectos de la Ingeniería de Software, en particular, habíamos desarrollado un modelopara el ocultamiento de la información y el requerimiento no funcional dela robustez, esto nos permitió sacar conclusiones sorprendentes sobre lacomplejidad de los algoritmos de eliminación, ver B. Bank, J. Heintz, G. Matera, J. L. Montaña, L. M. Pardo, A. Rojas Paredes, Quiz Games as a Model for Information Hiding, Journal of Complexity 34 1-29 (2016). Esta tesis describe un modelo de cómputo que se inspira en las nocionesde ocultamiento de la información y requerimientos no funcionales, entreotros conceptos importantes en Ingeniería de Software como las nociones deabstracción y el diseño de software. Nuestro modelo de cómputo permiteprobar cotas inferiores de complejidad exponencial para los algoritmos deeliminación. Mostramos que cualquier implementación orientada a objetos (y robusta) de algoritmos de eliminación es necesariamente ineficiente. Esteresultado muestra una sinergia existente entre Ingeniería del Software y Teoría de la Complejidad Algebraica.

Identificador:

https://hdl.handle.net/20.500.12110/tesis_n6348_RojasParedes