首页 > 试题广场 > 以下关于计算复杂度的说法中,正确的有( )。
[不定项选择题]
以下关于计算复杂度的说法中,正确的有( )。
  • 如果一个问题不存在多项式时间的算法,那它一定是 NP 类问题
  • 如果一个问题不存在多项式时间的算法,那它一定不是 P 类问题
  • 如果一个问题不存在多项式空间的算法,那它一定是 NP 类问题
  • 如果一个问题不存在多项式空间的算法,那它一定不是 P 类问题
首先明确 P 问题和 NP 问题的定义:P 问题的定义为 能够在多项式时间复杂度内解决的问题;NP 问题的定义为 能够在多项式时间复杂度内验证一个解是否正确的问题。但除去 P 问题之外的问题不一定都是 NP 问题,所以 A 错,B 对;既然空间复杂度不为多项式,那么时间复杂度一定不在多项式复杂度内,D 对,,同理 C 错
发表于 2019-10-10 14:17:43 回复(0)
BD
A 还记得图灵停机问题吗?那是一个NP-hard而不是NP问题 B 这是对的,因为P问题的定义是存在多项式时间的复杂度算法 C、D 时间复杂度和空间复杂度都是复杂度,是等价的。
发表于 2019-10-06 13:35:46 回复(0)