Complejidad computacional de votaciones y pactos

Abstract

En este trabajo presentamos tres problemas diferentes relacionados con la política, concretamente relacionados con votar y pactar. Primero definiremos algunos de los conceptos más importantes sobre complejidad, aproximabilidad y algoritmos genéticos. Luego, para cada problema presentamos resultados de complejidad y aproximabilidad, y desarrollamos algoritmos genéticos para resolverlos, analizando también la calidad de los resultados obtenidos.In this work, we present three different problems related to politics, specifically, voting and agreement problems. First, we define some of the most important concepts about complexity, approximability and genetic algorithms. Then, for each problem, we present complexity and approximability results, and we develop genetic algorithms to solve these problems, analyzing also the quality of the results we have obtained.