NP-complete

• P是指多项式时间内解决的问题
• NP是能在多项式时间验证答案正确与否的问题
• P是否等于NP是在问，如果一个问题我们能够在多项式时间内验证其答案的正确性，那么我们能否在多项式时间内解决它？
• 称问题L是NP-hard，如果任意一个NP问题都可以多项式规约到L。
• 如果一个NP-hard的问题L本身是NP的，则称L是NP-complete

ref
zhihu:怎么理解P问题与NP问题