算法| NP完全|问题3

设X是属于NP类的问题。那么以下哪一项是正确的？ （A） 对于X，没有多项式时间算法。 （B） 如果X可以在多项式时间内确定地求解，那么P=NP。 （C） 如果X是NP难的，那么它是NP完全的。

（D） X可能是不可判定的。 答复: （C） 说明： （A） 不正确，因为集合NP同时包含P（多项式时间可解）和NP完全。 （B） 不正确，因为X可能属于P（与（A）的原因相同） （C） 是正确的，因为NP完备集是NP和NP难集的交集。 （D） 是不正确的，因为所有的NP问题都可以在有限的运算集中判定。 这个问题的小测验