The Complexity of Computing Minimal Unidirectional Covering Sets
The Complexity of Computing Minimal Unidirectional Covering Sets
复制标题
计算最小单向覆盖集的复杂性
DOI：
10.1007/s00224-012-9437-9
复制
发表时间：
2013
影响因子：
0.5
通讯作者：
J. Rothe
中科院分区：
文献类型：
--
作者：
D. Baumeister;F. Brandt;F. Fischer;J. Hoffmann;J. Rothe
社会科学中的一个共同思路是根据某种二元支配关系来确定满足某些稳定性概念的替代方案集。在投票理论、博弈论和论证理论等不同领域都可以找到这样的例子。Brandt和Fischer（在Math.Soc.Sci. 56（2）：254-268，2008）证明了决定备选方案是否包含在某个包含最小单向（即，向上或向下）覆盖集合。对于这两个问题，我们都把这个下界提升到多项式层次，并给出了上界。与此相关，我们表明，各种其他自然问题的最小或最小尺寸的单向覆盖集是硬或完整的NP，coNP，和。我们的结果的一个重要后果是，无论是最小向上或最小向下覆盖集（即使保证存在）可以计算在多项式时间，除非P=NP。这与Brandt和Fischer的最小双向覆盖集是多项式时间可计算的结果形成鲜明对比。
A common thread in the social sciences is to identify sets of alternatives that satisfy certain notions of stability according to some binary dominance relation. Examples can be found in areas as diverse as voting theory, game theory, and argumentation theory. Brandt and Fischer (in Math. Soc. Sci. 56(2):254–268, 2008) proved that it is NP-hard to decide whether an alternative is contained in some inclusion-minimal unidirectional (i.e., either upward or downward) covering set. For both problems, we raise this lower bound to thelevel of the polynomial hierarchy and provide aupper bound. Relatedly, we show that a variety of other natural problems regarding minimal or minimum-size unidirectional covering sets are hard or complete for either of NP, coNP, and. An important consequence of our results is that neither minimal upward nor minimal downward covering sets (even when guaranteed to exist) can be computed in polynomial time unless P=NP. This sharply contrasts with Brandt and Fischer’s result that minimal bidirectional covering sets are polynomial-time computable.
登录
查看更多内容
识别启发式何时可以逼近最小顶点覆盖已完成以并行访问 NP
DOI：
--
发表时间：
2001
期刊：
RAIRO - Theoretical Informatics and Applications
影响因子：
--
作者：
E. Hemaspaandra;J. Rothe;Holger Spakowski
通讯作者：
Holger Spakowski
检查和评估的相对复杂性
影响因子：
0.5
作者：
L. Valiant
通讯作者：
L. Valiant
银行在锦标赛中的获胜者很难被认出
影响因子：
0.9
作者：
G. Woeginger
通讯作者：
G. Woeginger
SIGACT新闻复杂性理论专栏38
DOI：
--
发表时间：
2002
期刊：
SIGA
影响因子：
--
作者：
L. Hemaspaandra
通讯作者：
L. Hemaspaandra
布尔层次结构 II：应用
DOI：
--
发表时间：
1989
期刊：
SIAM journal on computing (Print)
影响因子：
--
作者：
Jin;T. Gundermann;J. Hartmanis;L. Hemaspaandra;V. Sewelson;K. Wagner;G. Wechsung
通讯作者：
G. Wechsung