NP问题(NP)，NP完全问题(NPC)，NP难问题(NP-hard)，三者之间的关系为（ ）。
A: NPC=NP∩NP-hard
B: NP=NPC∩NP-hard
C: NP-hard =NP∩NPC
D: NPÍNPCÍNP-hard
A: NPC=NP∩NP-hard
B: NP=NPC∩NP-hard
C: NP-hard =NP∩NPC
D: NPÍNPCÍNP-hard
举一反三
- NP-hard问题属于NP
- 下列说法错误的是（）? 所有的NP问题都可以转化为NP完全问题|NP完全问题大多来自于组合学、数论、逻辑学|NP完全问题是NP问题中难度最大的问题|所有NP完全问题构成的问题集合，记为NPC问题类
- 下列关于算法叙述正确的是（ ）。 A: NP完全问题比NP问题难。 B: NP-hard问题比NP完全问题难。 C: 旅行推销商（TSP）问题因为有解，所以是P问题。 D: NP问题也称为验证问题类。
- 何谓P、NP、NPC问题。
- 对于NP难问题和NP完全问题的说法正确的是() A: NP难问题和NP完全问题是等价的 B: NP难问题一定是NP类问题 C: 所有NP难问题都是NP完全问题 D: 所有NP完全问题都是NP难问题