P就是能在多项式时间内解决的问题，NP就是能在多项式时间验证答案正确与否的问题。

（多项式时间） 指在输入规模为 n时，算法的最坏时间复杂度可表示为 $O(n^k)$（k为常数）的算法。这类算法被视为“高效可解”问题的标准

所以P是否等于NP实质上就是在问，如果对于一个问题我能在多项式时间内验证其答案的正确性，那么我是否能在多项式时间内解决它？这个表述不太严谨，但通俗来讲就是如此。

再说说NP-hardness和NP-completenes. 这里涉及一个概念，不妨称为问题之间的归约。

可以认为各个问题的难度是不同的，表现形式为，如果我可以把问题A中的一个实例转化为问题B中的一个实例，然后通过解决问题B间接解决问题A，那么就认为B比A更难。

通过对归约过程做出限制可以得到不同类型的归约。其要求是转化问题的过程必须是多项式时间内可计算的。

到这为止NP-hardness和NP-completeness就很好理解了。称问题L是NP-hard，如果任意一个NP的问题都可以多项式规约到L。如果一个NP-hard的问题L本身就是NP的，则称L是NP-complete。这个定义可以推广到所有复杂度类。

所以compleness的直观解释就是，我能解决这个问题就相当于具备了用相同级别的计算资源解决这个复杂度类里所有问题的能力。