m solutions good, m-1 solutions better
m solutions good, m-1 solutions better
复制标题
m 解决方案好，m-1 解决方案更好
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
V. Kreinovich
中科院分区：
文献类型：
--
作者：
L. Longpré;W. Gasarch;G. Walster;V. Kreinovich
计算复杂性和可行性理论研究的主要目标之一是解释实验观察到的复杂性差异。经验证据表明，方程组的解越多，求解起来就越困难。同样，连续函数的全局最大值越多，定位它们就越困难。到目前为止，这些经验事实仅被部分形式化：即，已经表明具有两种或多种解决方案的问题比仅具有一种解决方案的问题更难解决。在本文中，我们扩展了这个结果，并表明对于每 m 个解决方案，具有恰好 m 个解决方案的问题比具有 m − 1 个解决方案的问题更难解决。改写奥威尔的“四条腿好，两条腿更好”，我们可以将这个结果描述为“m 个解决方案好，m−1 个解决方案更好”。数学科目分类：68Q17、68Q15、90C60、65G20 2 L. Longpre、V. Kreinovich、W. Gasarch、G.W.瓦尔斯特
One of the main objectives of theoretical research in computational complexity and feasibility is to explain experimentally observed difference in complexity. Empirical evidence shows that the more solutions a system of equations has, the more difficult it is to solve it. Similarly, the more global maxima a continuous function has, the more difficult it is to locate them. Until now, these empirical facts have been only partially formalized: namely, it has been shown that problems with two or more solutions are more difficult to solve than problems with exactly one solution. In this paper, we extend this result and show that for every m, problems with exactly m solutions are more difficult to solve than problems with m − 1 solutions. Rephrasing Orwell’s “Four legs good, two legs better”, we can describe this result as “m solutions good, m−1 solutions better”. Mathematics Subject Classification: 68Q17, 68Q15, 90C60, 65G20 2 L. Longpre, V. Kreinovich, W. Gasarch, G.W. Walster