N和NP问题
“P” refers to the class of problems that can be solved in polynomial time
“NP” refers to problems that can be solved in non- deterministic polynomial time
- P是能在多项式时间内解决的问题，
- NP是能在多项式时间验证答案正确与否的问题。
用大白话讲大概就是这样。P是否等于NP实质上就是在问，如果对于一个问题我能在多项式时间内验证其答案的正确性，那么我是否能在多项式时间内解决它？这个表述不太严谨，但通俗来讲就是如此。(2014, Wang)
什么是 polynomial time？
- 多项式级的复杂度：O(1),O(log(n)),O(n^a)等，因为它的规模n出现在底数的位置；
- 非多项式级的复杂度：O(a^n)和O(n!)型复杂度，其复杂度计算机往往不能承受。
