Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadas. Ingeniero Civil Matemático / Un conjunto de vértices de un grafo se dice convexo si contiene a los vértices de todos los caminos mínimos entre sus vértices. El problema de determinar si un grafo tiene una partición en p conjuntos convexos es NP-completo, pero hay diversas familias de grafos en las que se puede resolver en tiempo polinomial. El foco principal de este trabajo es estudiar el problema de la p-partición convexa en una familia de grafos definida recursivamente al reemplazar los vértices de un bosque por grafos de ésta. Esta familia resulta ser cerrada para subgrafos inducidos. Sin embargo, no queda totalmente determinada la familia de subgrafos prohibidos que determina a esta familia. Además, estos grafos resultan ser perfectos, por lo que varios problemas combinatoriales resultan tener soluciones polinomiales en esta familia. Además, se entrega un algoritmo polinomial para reconocer si un grafo pertenece a esta familia. Para atacar el problema de las particiones convexas en este contexto, combinaremos, mediante programación dinámica, particiones en subgrafos tales que sus particiones convexas son de tres tipos: todos los vértices, particiones en cliques y particiones en cliques más un conjunto localmente convexo. En el caso de las particiones en cliques, se entrega un algoritmo polinomial que lo resuelve. / Este trabajo ha sido parcialmente financiado por CONICYT mediante Proyecto Basal PFB 03

La presente investigación evalúa el concepto de computabilidad en la teoría de Alan Turing, justificándose por la existencia de opiniones divergentes entre diversos académicos, expresadas alrededor del significado de la tesis de Church-Turing, que trata a la función recursiva como equivalente al procedimiento efectivo. En la actualidad, operamos computadoras conectadas a la Internet, resultando habitual relacionar como computabilidad lo que se puede hacer en una computadora. Muy pocas veces asociamos a la computadora con la ejecución de un cálculo aritmético, tal vez porque disponemos de las máquinas calculadoras. En un sentido amplio, utilizamos la palabra computable como sinónimo de la obtención de un resultado utilizando una computadora. Cuando mencionamos cálculos, no sólo significa operaciones numéricas, también corresponde a operar símbolos, como ocurre cuando entendemos los elementos que nos rodean, los percibimos como fenómenos, incluso nos percatamos del ánimo de las personas y las interpretamos, aunque no siempre acertemos sobre los estados de ánimo.

Ingeniero Civil Matemático / La presente memoria se enmarca en el contexto de la computación distribuida. Esta es un área de las ciencias de la computación relativamente reciente, que surge ante la necesidad de un nuevo paradigma de computación, capaz de trabajar con cantidades masivas de datos, como son, por ejemplo, las redes sociales. En particular, se estudia la complejidad del problema CONEXIDAD de un grafo $G=(V,E)$ en el modelo computacional number-in-hand. Este problema consiste en decidir si un grafo $G$ es o no conexo. Por otro lado, a grandes rasgos, la complejidad que se considera aquí mide el largo de los mensajes (en bits) que los nodos deben comunicar para decidir CONEXIDAD. En primer lugar, se demuestra que la complejidad, en el caso en que el grafo $G$ es arbitrario, es al menos $f(n)$, donde $f(n) = \log n - (\log \log n +1+ \log n /n)$. Sin embargo, esta fórmula no aporta información alguna cuando el grafo $G$ posee $n<27$ nodos, pues $f(n) \leq 1$ para tales valores. Es decir, indica que la cantidad de bits que se tienen que comunicar es al menos $\leq 1$, lo que es evidente. Por esta razón, se profundiza el estudio analizando grafos pequeños, y se demuestra que 1 bit no es suficiente para decidir el problema en tal caso. Por otro lado, la cota expuesta se obtiene a partir de una reducción que construye un grafo de grado no acotado. Por lo tanto, $f(n)$ puede ser poco ajustada para la familia de grafos de grado acotado. Así pues, se complementa el trabajo restringiéndose a esta clase de grafos, con el fin de saber si en tal caso existe una mejor cota para la complejidad de CONEXIDAD en el modelo number-in-hand. Usando técnicas de complejidad comunicacional se encuentra una cota inferior de $\Omega(\log n)$. Más aún, se demuestra que esta cota es ajustada para esta clase de grafos.

Ingeniero Civil Matemático / El presente trabajo consiste en el estudio de la complejidad computacional en algunas redes de autómatas. En particular en el problema de decisión, que llamamos PER, el cual consiste en predecir cambios de estado en un nodo determinado cuando la red se actualiza según una regla determinada. Dentro de los primeros en introducir complejidad computacional a los autómatas celulares (CA) y sistemas relacionados podemos destacar a C. Moore [19] quien estudió la regla de la mayoría estricta en lattices d-dimensionales, y a T. Neary con D.Woods [23], que prueban la P-Complitud de la regla 110 en autómatas unidimensionales. Estos estudios son interesantes porque, por un lado, usualmente es muy difícil obtener caracterizaciones del comportamiento general de la dinámica de un autómata celular en el tiempo; y por otro lado, están relacionados con el procesamiento paralelo de la información y algoritmos, ya que algunos CA son capaces de emular una máquina de Turing universal. Luego, la idea es construir un puente entre estos dos aspectos del problema: la naturaleza de su dinámica y sus capacidades algorítmicas. Por lo general estos trabajos se enfocan en acotar el problema por arriba , determinando P-Complitud. Este trabajo es novedoso en el sentido que a lo anterior agregamos un acota- miento por abajo , buscando demostrar que cuando el problema no es P-Completo, entonces debe ser eficientemente paralelizable, es decir, pertenecer a la clase NC. Esto lo haremos va- riando primero la topología de la red considerando siempre un modo de iterar paralelo, y posteriormente determinando la influencia de distintos modos de iterar en la complejidad. En términos más concretos, estudiaremos la complejidad computacional de Bootstrap Percolation (Capítulo 2). El resultado principal es que, para esta regla, el problema de decisión PER está en NC si restringimos al grafo que define a la red a pertenecer a la familia que tiene grado máximo pequeño, y en caso contrario el problema es P-Completo. Luego, en el Capítulo 3, cambiaremos a la regla de la mayoría estricta, donde el principal resultado del capítulo será que para esta regla PER es P-Completo en la familia de grafos planares. Finalmente, en el cuarto capítulo estudiaremos cómo varían los resultados anteriores cuando consideramos distintos modos de actualizar los estados de la red. El resultado principal tendrá relación con los distintos modos de iterar considerando en cada nodo una función booleana AND u OR. Por último, daremos algunas conclusiones y problemas abiertos. El trabajo aquí expuesto ha permitido una publicación en Theoretical Computer Science llamado The complexity of Bootstrapping Percolation [10], una charla invitada (Winter FRAC 2012, París), una conferencia invitada (CA2012 Córcega), un artículo actualmente enviado a Advances in Applied Mathematics y otro en desarrollo.

No description available.

Ingeniero Civil Matemático / En muchos problemas que surgen en el contexto de consultar información en bases de datos estructuradas sobre grafos (como encontrar asociaciones semanticas en grafos RDF, encontrar emparejamientos exactos o aproximados the patrones de texto, realizar alineación de secuencias de texto, etc.) es un requerimiento común el buscar entidades unidas por secuencias de etiquetas relacionales de acuerdo a un patrón regular. Para este propósito, el lenguaje de consulta $\CRPQ(\S)$ ha sido propuesto para extender la altamente estudiada clase de consultas conjuntivas por caminos regulares (CRPQs por su sigla en inglés), la cual es insuficiente para esta tarea, realizando comparación de caminos con relaciones en la clase $\S$.\\ Poco es conocido acerca de la complejidad computacional precisa de la evaluación de consultas en $\CRPQ(\S)$ cuando $\S$ es una relación de interés por aparecer naturalmente en aplicaciones en bases de datos, como lo son \emph{subsecuencia} ($\ss$), \emph{sufijo} $(\suff)$ y \emph{subpalabra} ($\sw$). Esta pregunta es consecuentemente estudiada en esta tesis, proporcionando nuevas cotas de complejidad para la evaluación de consultas en los lenguajes $\CRPQ(\ss)$, $\CRPQ(\suff)$ y $\CRPQ(\sw)$. Se muestra que el primer lenguaje es dificil de ser practicable, construyendo una consulta en él cuya complejidad de evaluación es $\NP$-completo. Se muestra también que la evaluación de consultas en los últimos dos lenguajes puede realizarse en $\PSPACE$, mediante la reducción del problema a \emph{ecuaciones de palabras con restricciones regulares}. Adicionalmente, se muestra que la classe $\CRPQ(\suff)$ es práctica, construyendo un algoritmo de evaluación cuya complejidad, cuando la consulta es considerada una constante, está en $\NLOGSPACE$ , la cuál es una complejidad de evaluación estandar en este contexto.\\ Esta tesis plantea además interesantes preguntas teóricas sobre ecuaciones de palabras con restricciones regulares. Más precisamente, cuál es la complejidad de resolver ecuaciones fijas con restricciones como entrada, la cual es una pregunta abierta en la literatura al leal saber y entendimiento del autor. Un resultado es establecido para el caso más simple, mostrando una clase de ecuaciones cuya satisfacibilidad con restricciones regulares puede ser decidida en $\NLOGSPACE$.

Tesis para optar al grado de Doctor en Ciencias, Mención Computación / Los refinamientos actuales del análisis del peor caso sobre instancias con tamaño de entrada fijo consideran el orden de la entrada (por ejemplo, las subsecuencias ordenadas en una secuencia de números y las cadenas poligonales simples en las que puede dividirse una secuencia de puntos) o la estructura de la entrada (por ejemplo, la multiplicidad de los elementos en un multiconjunto y las posiciones relativas entre un conjunto de puntos en el plano), pero nunca, hasta donde sabemos, ambos al mismo tiempo. En esta tesis se proponen nuevas técnicas que combinan soluciones que se aprovechan del orden y la estructura de la entrada en una sola solución sinérgica para ordenar multiconjuntos, y para calcular la eficiencia de Pareto y la envoltura convexa de un conjunto de puntos en el plano. Estas soluciones sinérgicas se aprovechan del orden y la estructura de la entrada de tal forma que asintóticamente superan cualquier solución comparable que se aproveche solo de una de estas características. Como resultados intermedios, se describen y analizan varios algoritmos de mezcla: un algoritmo para mezclar secuencias ordenadas que es óptimo para cada instancia del problema; el primer algoritmo adaptativo para mezclar eficiencias de Pareto; y un algoritmo adaptativo para mezclar envolturas convexas en el plano. Estos tres algoritmos se basan en un paradigma donde las estructuras se dividen antes de ser mezcladas. Este paradigma es conveniente para extenderlo al contexto donde se responden consultas. Karp et al. (1998) describieron estructuras de datos diferidas como estructuras "perezosas" que procesan la entrada gradualmente a medida que responden consultas sobre los datos, trabajando la menor cantidad posible en el peor caso sobre instancias de tamaño fijo y número de consultas fijo. En esta tesis se desarrollan nuevas técnicas para refinar aún más estos resultados y aprovechar al mismo tiempo el orden y la estructura de la entrada y el orden y la estructura de la secuencia de consultas en tres problemas distintos: calcular el rango y la posici\'on de un elemento en un multiconjunto, determinar si un punto está dominado por la eficiencia de Pareto de un conjunto de puntos en el plano y determinar si un punto pertenece a la envoltura convexa de un conjunto de puntos en el plano. Las estructuras de datos diferidas que se obtienen superan todas las soluciones previas que solo se aprovechan de un subconjunto de estas características. Como una extensión natural a los resultados sinérgicos obtenidos en este trabajo para ordenar un multiconjunto, se describen estructuras de datos comprimidas que se aprovechan del orden y la estructura de la entrada para representar un multiconjunto, mientras se responden consultas del rango y la posición de elementos en el multiconjunto. / CONICYT-PCHA/Doctorado Nacional/2013-63130161, y los proyectos CONICYT Fondecyt/Regular nos 1120054 y 1170366

The analysis of the computational aspects of strategic situations is a basic field in Computer Sciences. Two main topics related to strategic games have been developed. First, introduction and analysis of a class of games (so called angel/daemon games) designed to asses web applications, have been considered. Second, the problem of isomorphism between strategic games has been analysed. Both parts have been separately considered. Angel-Daemon Games A service is a computational method that is made available for general use through a wide area network. The performance of web-services may fluctuate; at times of stress the performance of some services may be degraded (in extreme cases, to the point of failure). In this thesis uncertainty profiles and Angel-Daemon games are used to analyse servicebased behaviours in situations where probabilistic reasoning may not be appropriate. In such a game, an angel player acts on a bounded number of ¿angelic¿ services in a beneficial way while a daemon player acts on a bounded number of ¿daemonic¿ services in a negative way. Examples are used to illustrate how game theory can be used to analyse service-based scenarios in a realistic way that lies between over-optimism and over-pessimism. The resilience of an orchestration to service failure has been analysed - here angels and daemons are used to model services which can fail when placed under stress. The Nash equilibria of a corresponding Angel-Daemon game may be used to assign a ¿robustness¿ value to an orchestration. Finally, the complexity of equilibria problems for Angel-Daemon games has been analysed. It turns out that Angel-Daemon games are, at the best of our knowledge, the first natural example of zero-sum succinct games. The fact that deciding the existence of a pure Nash equilibrium or a dominant strategy for a given player is Sp 2-complete has been proven. Furthermore, computing the value of an Angel-Daemon game is EXP-complete. Thus, matching the already known complexity results of the corresponding problems for the generic families of succinctly represented games with exponential number of actions. Game Isomorphism The question of whether two multi-player strategic games are equivalent and the computational complexity of deciding such a property has been addressed. Three notions of isomorphisms, strong, weak and local have been considered. Each one of these isomorphisms preserves a different structure of the game. Strong isomorphism is defined to preserve the utility functions and Nash equilibria. Weak isomorphism preserves only the player preference relations and thus pure Nash equilibria. Local isomorphism preserves preferences defined only on ¿close¿ neighbourhood of strategy profiles. The problem of the computational complexity of game isomorphism, which depends on the level of succinctness of the description of the input games but it is independent of the isomorphism to consider, has been shown. Utilities in games can be given succinctly by Turing machines, boolean circuits or boolean formulas, or explicitly by tables. Actions can be given also explicitly or succinctly. When the games are given in general form, an explicit description of actions and a succinct description of utilities have been assumed. It is has been established that the game isomorphism problem for general form games is equivalent to the circuit isomorphism when utilities are described by Turing Machines; and to the boolean formula isomorphism problem when utilities are described by formulas. When the game is given in explicit form, it is has been proven that the game isomorphism problem is equivalent to the graph isomorphism problem. Finally, an equivalence classes of small games and their graphical representation have been also examined.