Es NP-completo calcular la comunidad entre los objetos sobre los que una colección de agentes ha realizado una acción

Resumen

En este trabajo demostramos que el problema que llamamos Comunalidad de grupos sociales (SGC por sus siglas en inglés) es NP-completo. Este problema consulta la comunalidad entre los objetos tocados por una colección de agentes que ejecutan acciones. Aunque se presenta naturalmente en varios contextos e.g., perfilar el comportamiento de un conjunto de usuarios de un sistema, SGC ha sido, acorde al conocimiento de los autores, ignorado. Nuestra demostración consiste en una reducción de Karp a partir del problema conocido como Longest Common Subsequence (LCS). Probamos también que un caso especial, al que llamamos 2-SGC, donde la comunalidad entre las acciones está limitada a pares de agentes, sigue siendo NP-completo. Para probar 2-SGC, nuestra reducción parte del problema conocido como Hitting Set. Antes de concluir con el artículo, especulamos que la versión de optimización de SGC es NP-duro, dando indicaciones de cómo realizar la demostración necesaria.