论文标题
可行的算法选项，用于创建和调整新兴软件系统
Viable Algorithmic Options for Creating and Adapting Emergent Software Systems
论文作者
论文摘要
鉴于现代软件系统的复杂性，这种系统能够自主修改自己，即自适应，并通过最少的人类监督来自主修改。至关重要的是，这种适应性两者都会导致可靠的系统，并在所需的内存和运行时合理地缩放到非平凡的系统。在本文中，我们采用计算复杂性分析来评估算法选项，以相对于几种流行的精确和近似有效的可溶解性，可靠创建和适应新兴软件系统。我们表明，当对软件系统结构没有限制时，所有输入都无法解决。当在多项式时间内，将软件系统限制在运行（可以根据系统需求验证）时，这种棘手的性能继续相对于所有有效的精确和近似可溶性类型而保持。此外，在对软件系统结构的各种额外限制下，无论是单独和许多组合，我们的两个问题都保持不适。话虽这么说，我们还提供了一组其他限制，这些限制确实可以使这两个问题产生障碍，并且间接证据表明，新兴软件系统适应在计算上比新兴软件系统创建更容易。
Given the complexity of modern software systems, it is of great importance that such systems be able to autonomously modify themselves, i.e., self-adapt, with minimal human supervision. It is critical that this adaptation both results in reliable systems and scales reasonably in required memory and runtime to non-trivial systems. In this paper, we apply computational complexity analysis to evaluate algorithmic options for the reliable creation and adaptation of emergent software systems relative to several popular types of exact and approximate efficient solvability. We show that neither problem is solvable for all inputs when no restrictions are placed on software system structure. This intractability continues to hold relative to all examined types of efficient exact and approximate solvability when software systems are restricted to run (and hence can be verified against system requirements) in polynomial time. Moreover, both of our problems when so restricted remain intractable under a variety of additional restrictions on software system structure, both individually and in many combinations. That being said, we also give sets of additional restrictions that do yield tractability for both problems, as well as circumstantial evidence that emergent software system adaptation is computationally easier than emergent software system creation.
