P,NP,NP-C,NP-hard问题

P问题：在确定的机器上，在多项式时间内能够解决的问题

NP问题：在多项式时间内可以验证的判定问题。

NP-Hard问题：问题A称为NP-Hard问题，如果对于任意一个NP问题，都可以在多项式时间内规约为A。

NP-C：既是NP问题，又是NP-Hard问题

#P：全是计数问题。

NP都是判定问题，NP-Hard都是优化问题。