P、NP、NPC和NP-Hard問題的通俗化解釋和詳細區分

首先需要了解如下概念：

多項式級的複雜度：O(1), O(n),O(n^2),O(lg(n)),O(nlg(n))

非多項式級的複雜度：O(2^n),O(n!)

P問題：可以在多項式時間内找到解決該問題的算法

NP問題：可以在多項式的時間裡驗證該問題的一個解

NPC問題：是一個NP問題，并且所有的NP問題都可以約化到該問題

NP-hard問題：不一定是一個NP問題，但所有的NP問題都可以約化到該問題

詳細檢視：http://www.matrix67.com/blog/archives/105

詳細檢視：http://blog.sina.com.cn/s/blog_538ee63f0101fguy.html