NOIP 提高 2013 第一轮 第 19 题：CCFNOIP2013初赛提高组C++语言试题

题目

（   ）属于 NP 类问题。

答案

A、B

题解

考点定位

本题考「NP 类定义（不定项）」,对应大纲 4.1.1 复杂度类（难度【4】）。

解题过程

NP = 「可在多项式时间内验证解」的问题类。P ⊆ NP：

• A P 类问题属于 NP ✓；
• B 任何 P 类问题 ✓（同理）；
• C 非 P 的问题必属 NP ✗（可能连 NP 都不是）；
• D 指数时间可解 ✗（指数可解不保证多项式可验证）。

答案：A、B。

易错提醒

① P ⊆ NP，是否相等是千年难题；② NP ≠ 「非多项式」——是「非确定性多项式时间」。