P 问题和 NP 问题
P 和 NP 问题：想当初计算理论是真的没学太明白。 P（Polynominal）多项式时间解决的问题。规模 n 出现在底数的位置，如 O(1)，O(logn)，O(n) 等 NP（Non-deterministicPolynomial）非多项式时间解决的问题，能在多项式时间验证。规模 n 出现在顶部的位置，如 O(n!)，O(2^n) 等 NPC（Complete）问题，首先是 NP 问题，然后所有 NP 问题都可以归约到它，归约就是把一个问题转化为另一个问题，这也就是说 NPC 问题是 NP 问题中最难的 NP-Hard 问题，首先所有 NP 问题都可以约化到它，然后它不一定是 NP 问题，也就是描述了一种类至少和 NP 中最难的问题一样难的问题，且这个问题不一定是 NP 问题
阅读更多