On the Hardness of Problems Involving Negator Relationships in an Artificial Hormone System
This work addresses algorithmic challenges in distributed systems for researchers and practitioners, but it is incremental as it builds on prior studies of NP-completeness in this context.
The paper tackles the increased computational complexity in an Artificial Hormone System due to negator hormones, showing that problems like Negator-Path and Negator-Sat are NP-complete and introducing a new problem, Negator-Stability, to explain why these issues are hard to solve algorithmically.
The Artificial Hormone System (AHS) is a self-organizing middleware to allocate tasks in a distributed system. We extended it by so-called negator hormones to enable conditional task structures. However, this extension increases the computational complexity of seemingly simple decision problems in the system: In [1] and [2], we defined the problems Negator-Path and Negator-Sat and proved their NP-completeness. In this supplementary report to these papers, we show examples of Negator-Path and Negator-Sat, introduce the novel problem Negator-Stability and explain why all of these problems involving negators are hard to solve algorithmically.