CHAPTER7 NP完全性 | shenghai's blog | shxt

[codershenghai]

http://www.zhangshenghai.com/posts/64398/

P问题、NP问题、NPC问题的概念老师上课时强调过本章对于概念要特别清楚，因此首先给出这三个问题的概念： P问题：能够在多项式时间内解决的问题。 NP问题：能够在多项式时间内验证一个解的正确性的问题。 NPC问题：当一个问题满足下面两个条件的时候，那么这个问题是NPC问题。 首先，它是NP问题。 其次，所有其他的NP问题都能够在多项式时间内归约到此问题上（NP-hard）。 NPC问题