00:02
NP完全性
Approaches to Understanding and Addressing NP-Completeness | SPA Reporter: Jiakai Gu
Date: Dec 25th, 2023
Date: Dec 25th, 2023
Table of contents
current
Table of contents
next
No notes.
NP完全性
Approaches to Understanding and Addressing NP-Completeness | SPA Reporter: Jiakai Gu
Date: Dec 25th, 2023
Date: Dec 25th, 2023
1
Table of contents
2
易解的问题与难解的问题
多项式时间算法：以多项式为时间复杂度的算法
易解的问题：有多项式时间的算法，例子：线性搜索、快速排序…
难解的问题：不存在多项式时间的算法，例子：TSP问题、Hamilton回路…
| 算法类型 | 定义 | 例子 | 特点 |
|---|---|---|---|
| 多项式时间算法 | 以多项式为时间复杂度的算法 | 线性搜索、快速排序 | 随输入规模增加，时间以渐进方式增长 |
| 非多项式时间算法 | 不存在多项式时间的算法 | TSP问题、Hamilton回路 | 随输入规模增加，时间以陡峭方式增长 |
3
判定问题
判定问题指的是那些答案为“是”或“否”的问题。
写出下述优化问题对应的判定问题： 1、最长回路问题：任给无向图G，求G中一条最长的初级（即顶点不重复的）回路 对应的判定问题：给定无向图G和一个长度L，是否存在一条长度至少为L的初级回路？写出下述优化问题对应的判定问题： 1、最长回路问题：任给无向图G，求G中一条最长的初级（即顶点不重复的）回路 对应的判定问题：给定无向图G和一个长度L，是否存在一条长度至少为L的初级回路？
注：判定问题的形式是将一个优化问题转化为一个有明确“是”或“否”答案的问题。
4
NP类
P类问题(P Problems，Polynomial Time Problems)：如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。【可以快速找到解的问题】
NP问题（NP Problems，Nondeterministic Polynomial Time Problems）不是非P类问题。NP问题是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。【可以快速验证一个给定解是否正确的问题，但找到解的过程可能并不快速。】
Q1、如何理解NP问题不是非P类问题？非P类问题和NP问题的关系是啥？
Q2、P问题是易解问题？NP问题是难解问题？
5
课堂回顾
判断题
1、所有的P类问题都是NP问题。 2、如果一个问题是NP问题，那么它一定是难解问题。 3、NP问题是指那些可以在多项式时间内找到解的问题。 4、非P类问题是指那些不能在多项式时间内解决的问题。 5、所有NP问题都有已知的多项式时间算法解决方案。 6、如果一个问题可以在多项式时间内验证一个解的正确性，那么这个问题一定属于NP问题。 7、如果P=NP被证明为真，那么所有NP问题都可以被归类为易解问题。 8、二分查找是一个NP问题，因为它可以在多项式时间内解决。 9、在多项式时间内无法验证解的正确性的问题不属于NP问题。1、所有的P类问题都是NP问题。 2、如果一个问题是NP问题，那么它一定是难解问题。 3、NP问题是指那些可以在多项式时间内找到解的问题。 4、非P类问题是指那些不能在多项式时间内解决的问题。 5、所有NP问题都有已知的多项式时间算法解决方案。 6、如果一个问题可以在多项式时间内验证一个解的正确性，那么这个问题一定属于NP问题。 7、如果P=NP被证明为真，那么所有NP问题都可以被归类为易解问题。 8、二分查找是一个NP问题，因为它可以在多项式时间内解决。 9、在多项式时间内无法验证解的正确性的问题不属于NP问题。
6
Thank you for listening!
7