NOIP 提高组初赛 · NOIP 2012 提高组初赛试题 第 20 题

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

这题考 P 和 NP 类问题的定义区别。拿到题先想：P 类要求有多项式时间算法，NP 类只要求解能被多项式时间验证。既然题干说“不存在多项式时间算法”，那它肯定不在 P 类里；至于 NP 类，得看它是否满足“可验证”这个核心条件，而不是看有没有求解算法，所以 A、C 这种把“无算法”硬套到 NP 上的选项直接排除。

最容易掉进 A、C 两个坑：把“不存在多项式算法”当成 NP 的充分条件。记住 NP 的关键是“可验证”，不是“无算法”。另外，P 类问题天然隐含多项式空间，所以只要时间复杂度不是多项式，空间肯定也不是多项式，D 选项看似绕弯子其实逻辑很顺，别被“空间”二字绕晕。

P 与 NP 复杂度

• A：无多项式算法 → 不一定是 NP（NP 要求可验证）✗
• B：无多项式算法 → 一定不是 P（P 要求有多项式算法）✓
• C：无多项式空间算法 → 不一定是 NP ✗
• D：无多项式空间算法 → 一定不是 P（P 隐含多项式空间）✓

正确答案：B、D

考频与趋势：关联知识点“计算机发展史”在题库中共考过 29 题，覆盖 3 个考试级别（2007-2020）；逐年分布：2007 年 5 题、2008 年 6 题、2009 年 2 题、2010 年 2 题、2011 年 3 题、2012 年 9 题、2013 年 1 题、2020 年 1 题；分赛事：NOIP 提高组 初赛 15 题、NOIP 普及组 初赛 13 题、CSP 提高级 1 题。其中 2012 年考了 9 题，是这十年的小高峰，说明命题人当年对复杂度基础概念查得紧。

预测：从数据看，2013 年和 2020 年都只有 1 题，2007-2012 分布较散，暂无足够依据预测未来具体年份的考频，但“P 与 NP”这类基础概念在 NOIP 提高组初赛里始终占有一席之地，建议继续夯实。