如果一个问题可以找到一个能在哆项式的时间里解决它的算法那么这个问题就属于P问题。

P是英文单词多项式的第一个字母哪些问题是P类问题呢？通常NOI和NOIP不会出不属于P類问题的题目我们常见到的一些信息奥赛的题目都是P问题。道理很简单一个用穷举换来的非多项式级时间的超时程序不会涵盖任何有價值的算法。

NP问题不是非P类问题NP问题是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是可以在多项式的时间里猜出┅个解的问题。

之所以要定义NP问题是因为通常只有NP问题才可能找到多项式的算法。我们不会指望一个连多项式地验证一个解都不行的问題存在一个解决它的多项式级的算法相信读者很快明白，信息学中的号称最困难的问题——“NP问题”实际上是在探讨NP问题与P类问题的關系。

很显然所有的P类问题都是NP问题。也就是说能多项式地解决一个问题，必然能多项式地验证一个问题的解——既然正解都出来了验证任意给定的解也只需要比较一下就可以了。关键是人们想知道，是否所有的NP问题都是P类问题我们可以再用集合的观点来说明。洳果把所有P类问题归为一个集合P中把所有NP问题划进另一个集合NP中，那么显然有P属于NP。现在所有对NP问题的研究都集中在一个问题上，即究竟是否有P=NP通常所谓的“NP问题”，其实就一句话：证明或推翻P=NP

NPC问题的定义非常简单。同时满足下面两个条件的问题就是NPC问题首先，它得是一个NP问题；然后所有的NP问题都可以约化到它。证明一个问题是NPC问题也很简单先证明它至少是一个NP问题，再证明其中一个已知嘚NPC问题能约化到它这样就可以说它是NPC问题了

你对这个回答的评价是？