在计算机科学里，有时间复杂度的概念，然后就有P,NP,NPC,NP-hard的概念，平常大家说的这个题是np的，只能搜了，其实是理解错了np的概念，首先要明确np并不是“不是p”的意思，p大家都清楚是指有多项式时间的算法，而np看全称是“nondeterministic polynomial time”，是说非确定多项式时间，进一步说，正如图片上说的p是属于np的，所有p问题都是np问题。

    这或许是众多OIer最大的误区之一。 你会经常看到网上出现“这怎么做，这不是NP问题吗”、“这个只有搜了，这已经被证明是NP问题了”之类的话。你要知道，大多数人此时所说的NP问题其实都是指的NPC问题。他们没有搞清楚NP问题和NPC问题的概念。NP问题并不是那种“只有搜才行”的问题，NPC问题才是。好，行了，基本上这个误解已经被澄清了。下面的内容都是在讲什么是P问题，什么是NP问题，什么是NPC问题，你如果不是很感兴趣就...