Intractable problems in control theory
Intractable problems in control theory
复制标题
控制理论中的棘手问题
DOI：
10.1109/cdc.1985.268670
复制
发表时间：
1985
期刊：
影响因子：
--
通讯作者：
J. Tsitsiklis
中科院分区：
文献类型：
--
作者：
C. Papadimitriou;J. Tsitsiklis
本文运用复杂性理论的概念和方法，研究了分散决策中明显的棘手问题。我们首先建立，离散版本的一个重要的范例，这一领域，由Witsenhausen提出的，是NP完全的，从而解释了失败的文献中报道的攻击计算。在其余的文件中，我们表明，计算的离散版本的控制问题的棘手性可能意味着，有没有令人满意的（连续）算法的连续版本。为此，我们开发了一个理论的连续算法及其复杂性，和分析方法，这可以证明自己很有趣。
This paper is a study of the apparent intractability of problems in decentralized decision-making, using the concepts and methods of Complexity Theory. We first establish that the discrete version of an important paradigm for this area, proposed by Witsenhausen, is NP-complete, thus explaining the failures reported in the literature to attack it computationally. In the rest of the paper we show that the computational intractability of the discrete version of a control problem can imply that there are no satisfactory (continuous) algorithms for the continuous version. To this effect, we develop a theory of continuous algorithms and their complexity, and an analytical methodology, which can prove quite interesting by themselves.