首页 > 试题广场 >

以下关于计算复杂度的说法中，正确的有（ ）。

[不定项选择题]
以下关于计算复杂度的说法中，正确的有（ ）。 
  • 如果一个问题不存在多项式时间的算法，那它一定是 NP 类问题
  • 如果一个问题不存在多项式时间的算法，那它一定不是 P 类问题
  • 如果一个问题不存在多项式空间的算法，那它一定是 NP 类问题
  • 如果一个问题不存在多项式空间的算法，那它一定不是 P 类问题
查看正确选项
添加回答
Venμs头像 Venμs
首先明确 P 问题和 NP 问题的定义：P 问题的定义为 能够在多项式时间复杂度内解决的问题；NP 问题的定义为 能够在多项式时间复杂度内验证一个解是否正确的问题。但除去 P 问题之外的问题不一定都是 NP 问题，所以 A 错，B 对；既然空间复杂度不为多项式，那么时间复杂度一定不在多项式复杂度内，D 对，，同理 C 错
发表于 2019-10-10 14:17:43 回复(0)
Leven_头像 Leven_
BD
A 还记得图灵停机问题吗？那是一个NP-hard而不是NP问题 B 这是对的，因为P问题的定义是存在多项式时间的复杂度算法 C、D 时间复杂度和空间复杂度都是复杂度，是等价的。
发表于 2019-10-06 13:35:46 回复(0)
提交观点

问题信息

提高 C++ Pascal OI常识
来自：NOIP2012初赛提高组
上传者：牛客309901号
难度：
2条回答 3732浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号