Computability and Complexity of opinion dynamics

Abstract

In this work, we discuss and prove several theoretical results related to computability and complexity properties of an opinion dynamics model we define. We also try to find low-complexity heuristics and algorithms which let us obtain approximate solutions of an NP-complete problem based on our model, and run simulations to determine to what extent these heuristics are effective. Although we conclude that most practical problems related to our model are undecidable in the infinite case and PSPACE-complete or NP-complete in the finite case, the obtained low-complexity algorithms are effective at solving instances whose structure and properties are similar to those of real-world examples.En este trabajo, se abordan y demuestran varios resultados teóricos relacionados con las propiedades de computabilidad y complejidad de un modelo de dinámica de opiniones que definimos. También intentamos encontrar heurísticas y algoritmos de baja complejidad que nos permitan obtener soluciones aproximadas de un problema NP-completo basado en nuestro modelo, y ejecutamos simulaciones para determinar en qué medida estas heurísticas son efectivas. A pesar de que concluimos que la mayoría de problemas prácticos relacionados con nuestro modelo son indecidibles en el caso infinito y PSPACE-completos o NP-completos en el caso finito, los algoritmos de baja complejidad obtenidos son efectivos resolviendo instancias cuya estructura y propiedades son parecidas a las de ejemplos del mundo real.