关于问题的算法复杂性,下列叙述正确的是( )。
A: 问题求解算法的时间复杂度是该问题实例规模n的多项式函数,则这种可以在多项式时间内解决的问题称为P类问题。
B: 不能在多项式时间内求解的问题为NP问题。
C: NP问题就是时间复杂性为O(2n)的问题。
D: NP问题就是时间复杂性为O(n!)的问题。
E: NP问题都是不可解的。
F: NP问题虽然不能在多项式时间内求解,但对于所有解,都可以在多项式时间内验证它是否为问题的解。
A: 问题求解算法的时间复杂度是该问题实例规模n的多项式函数,则这种可以在多项式时间内解决的问题称为P类问题。
B: 不能在多项式时间内求解的问题为NP问题。
C: NP问题就是时间复杂性为O(2n)的问题。
D: NP问题就是时间复杂性为O(n!)的问题。
E: NP问题都是不可解的。
F: NP问题虽然不能在多项式时间内求解,但对于所有解,都可以在多项式时间内验证它是否为问题的解。
举一反三
- 关于问题的算法复杂性,下列叙述正确的是( )。 A: 问题求解算法的时间复杂度是该问题实例规模n的多项式函数,则这种可以在多项式时间内解决的问题称为P类问题。 B: 不能在多项式时间内求解的问题为NP问题。 C: NP问题就是时间复杂性为O(2n)的问题。 D: NP问题就是时间复杂性为O(n!)的问题。 E: NP问题都是不可解的。 F: NP问题虽然不能在多项式时间内求解,但对于所有解,都可以在多项式时间内验证它是否为问题的解。
- 关于问题的算法复杂性,下列叙述正确的是_________。 A: NP问题都是不可解的。 B: NP问题虽然不能在多项式时间内求解,但对于所有解,都可以在多项式时间内验证它是否为问题的解。 C: 问题求解算法的时间复杂度是该问题实例规模n的多项式函数,则这种可以在多项式时间内解决的问题称为P类问题。 D: NP问题就是时间复杂性为O(n!)的问题。
- 下列说法不正确的是_____。? NP类问题是不确定能够找到多项式时间复杂性算法进行求解的问题|P类问题是总能找到一个多项式时间复杂性算法进行求解的问题|NP类问题是一定找不到多项式时间复杂性算法进行求解的问题|NP类问题虽然是不确定能找到多项式时间复杂性算法进行求解,但一定能找到多项式时间复杂性算法进行“解”的正确性验证的问题
- P类问题、NP类问题、NPC类问题是计算机科学领域关于可求解性可计算性很重要的概念。关于P、NP和NPC类问题,下列说法不正确的是_____。 A: P类问题是总能找到一个多项式时间复杂性算法进行求解的问题 B: NP类问题是一定找不到多项式时间复杂性算法进行求解的问题 C: NP类问题是不确定能够找到多项式时间复杂性算法进行求解的问题 D: NP类问题虽然是不确定能找到多项式时间复杂性算法进行求解,但一定能找到多项式时间复杂性算法进行“解”的正确性验证的问题
- 根据问题求解的算法时间复杂性,下列叙述中错误的是( ) A: 可以在多项式时间内解决的问题属于P类问题 B: NP问题为非确定性多项式问题 C: NP-hard问题永远都是不可解的 D: NP-hard问题可以用枚举法验证解,但时间复杂性太大