Question

Noip2013提高组初赛有一道题，能不能举个反例

（）属于NP问题，。。。D、任何一个在（输入规模）指数时间内能够解决的问题
答案不选D

Answer 1

反例例：可能是p类问题。

P类问题（Polynomial）：

一个问题，任何数据都有多项式时间复杂度的算法。

多项式复杂度，n在底数上：

O(1)，O(logn)，O(n)，O(nlogn)，O(n^a)

非多项式复杂度（所谓的指数级）：

O(a^n)，O(n!)

（NP就是能在多项式时间验证答案正确与否的问题。对于一个问题我能在多项式时间内验证其答案的正确性，那么我是否能在多项式时间内解决它？答案是不确定的，所以n不一定等于np还没有证明）

追问

反例例：可能是p类问题。
然而p类问题也是np问题啊

追答

不好意思，写错了！！ P类问题一定属于NP问题 

反例应该是 ： np-HARD 问题。 NP-hard 不能在多项式时间内解决 但可能在指数级范围内解决！！