下列问题不为NP-完全问题的为()
A: SAT问题
B: 图灵机停机问题
C: 旅行商问题
D: 顶点覆盖问题
A: SAT问题
B: 图灵机停机问题
C: 旅行商问题
D: 顶点覆盖问题
举一反三
- 下列问题,不是NP-完全问题的是 A: SAT 问题 B: Post对应问题 C: 顶点覆盖问题 D: 哈密顿回路问题
- 下列关于算法叙述正确的是( )。 A: NP完全问题比NP问题难。 B: NP-hard问题比NP完全问题难。 C: 旅行推销商(TSP)问题因为有解,所以是P问题。 D: NP问题也称为验证问题类。
- 对于NP难问题和NP完全问题的说法正确的是() A: NP难问题和NP完全问题是等价的 B: NP难问题一定是NP类问题 C: 所有NP难问题都是NP完全问题 D: 所有NP完全问题都是NP难问题
- 关于P问题、NP问题、NP完全问题,下面说法正确的是( ) A: P=NP B: 有的NP问题无法约化为可满足性问题 C: NP完全问题都是NP问题 D: NP问题都是NP完全问题
- 如果问题A属于NP完全问题,其子问题一定属于NP完全