NOIP 提高组初赛 · NOIP 2013 提高组初赛试题 第 19 题

（ ）属于 NP 类问题。

这道题考复杂度理论里P和NP的关系。记住核心结论：P类问题一定包含在NP里，所以只要选项里出现P类问题，大概率就是对的。

很多同学把NP想成'非P'，觉得P和NP是互补的，或者认为NP就是指数时间能解的。其实NP定义的是'多项式时间可验证'，和能不能在多项式时间解开是两码事。P⊆NP，但NP是否等于P至今未解。最容易错选C，以为‘不属于P的一定属于NP'，其实还有不可判定问题。D也常错，因为NP不要求求解时间多项式，只要求验证时间多项式，指数时间求解的问题不一定在NP里。

考点定位

这道题属于算法复杂度理论，核心是理解P类问题与NP类问题的定义及其包含关系。这是NOIP、CSP等考试中反复出现的高频考点，命题人喜欢用看似绝对化的描述（如“任何一个不属于P的问题”）来挖坑。

概念拆解（人话版）

• P类问题：能在多项式时间内求解的问题。比如排序、最短路径这类经典算法，时间随输入规模呈多项式增长。
• NP类问题：能在多项式时间内验证一个解是否正确的问题。注意，NP不要求我们能在多项式时间内找到解，只要求：如果有人给你一个答案，你很快就能核对它对不对。典型的NP问题是旅行商问题、子集和问题。
• 关键关系：P ⊆ NP。因为如果一个问题能在多项式时间内求解，那当然也能在多项式时间内验证（直接把解算出来再核对）。但NP是否等于P，是计算机科学七大未解之谜之一。