论文标题
关于涉及人造激素系统中否定关系的问题的硬度
On the Hardness of Problems Involving Negator Relationships in an Artificial Hormone System
论文作者
论文摘要
人造激素系统（AHS）是一种自组织的中间件，可以在分布式系统中分配任务。我们通过所谓的消极激素扩展了它，以实现有条件的任务结构。但是，这一扩展增加了系统中看似简单的决策问题的计算复杂性：在[1]和[2]中，我们定义了否定路径和否定器-SAT的问题，并证明了他们的NP完整性。在这些论文的补充报告中，我们展示了Negator-Path和Negator-Sat的例子，介绍了新的问题否定器稳定性，并解释了为什么所有这些涉及否定者的问题都难以求解算法。
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.
