NP类问题不能在多项式时间内解决。( )
举一反三
- 关于问题的算法复杂性,下列叙述正确的是()。 A: NP问题就是时间复杂性为O(2n)的问题。 B: NP问题都是不可解的。 C: 问题求解算法的时间复杂度是该问题实例规模n的多项式函数,则这种可以在多项式时间内解决的问题称为P类问题。 D: NP问题虽然不能在多项式时间内求解,但对于所有解,都可以在多项式时间内验证它是否为问题的解。 E: NP问题就是时间复杂性为O(n!)的问题。 F: 不能在多项式时间内求解的问题为NP问题。
- 关于问题的算法复杂性,下列叙述正确的是( )。 A: 问题求解算法的时间复杂度是该问题实例规模n的多项式函数,则这种可以在多项式时间内解决的问题称为P类问题。 B: 不能在多项式时间内求解的问题为NP问题。 C: NP问题就是时间复杂性为O(2n)的问题。 D: NP问题就是时间复杂性为O(n!)的问题。 E: NP问题都是不可解的。 F: NP问题虽然不能在多项式时间内求解,但对于所有解,都可以在多项式时间内验证它是否为问题的解。
- 下列关于NP完全问题的描述,正确的是:() A: 如果一个NP完全问题能在多项式时间内得到解决,那么NP完全问题中的每一个问题都可以在多项式时间内求解 B: 如果一个NP完全问题能在多项式时间内得到解决,那么NP完全问题中的大部分问题都可以在指数时间内求解 C: 如果一个NP完全问题能在多项式时间内得到解决,那么NP完全问题中的每一个问题都可以在指数时间内求解 D: 如果一个NP完全问题能在多项式时间内得到解决,那么NP完全问题中的大部分问题都可以在多项式时间内求解
- 如果一个NP完全问题能在多项式时间内得到解决,那么NP中的每一个问题都可以在多项式时间内求解。
- 、NP问题是不能在多项式时间复杂性解决的可判定问题( ).