NP Completeness

Intro

NP: Non-deterministic Polynomial-time

P = NP:

什么是 NP问题中最难的部分->NP-complete

性感的性质 可以将其他问题归约到 NP-complete 问题

只要解决任意一个 NP-complete 问题 其他 NP-complete 问题也就解决了

难易和快慢：

所有不能用多项式时间解决的问题都是难的问题

只要是能用多项式时间解决的问题都是容易的问题 不需要具体比较他们之间的快慢来进行定义

证明一个问题是否是 NP-complete 问题

拿一个已知的 NP-complete 问题进行归约 如果能用多项式时间复杂度归约 那么这个问题也就是 NP-complete 问题