当前位置：网站首页>P/NP/NP完全/NP难

P/NP/NP完全/NP难

2022-07-21 05:15:00 【kurok_】

这是一类问题，有一个共同的特性：如果其中一个是多项式可解的，那么其他的问题也是多项式可解的。

确定性算法的概念：重复相同的输入，每一步执行选择和获得的输出从不改变。

判定问题的P类是：他们的Yes/No解可以用确定性算法在多项式步数内得到判定。也是接触到的大多数算法的类别，如最短路径。

NP类问题简单来说，就是给定一个解后，能在多项式时间内确定这个解是否正确的问题类。

"NP完全"表示NP中判定问题的一个子类，如果他们中的一个被证明用多项式时间确定性算法可解，那么NP中的所有问题都能用多项式时间确定性算法可解，即NP=P。

为了证明一个问题是NP完全的：

1.需要证明它在NP中，

2.且对于NP中的每一个问题i，都可以在多项式时间归约到该问题

如果只满足2的话，就是NP难问题。

另外还有一些定义概念，可满足性和不确定性算法的两个阶段，不展开。

菜鸟新手，欢迎指正文章错误。

版权声明
本文为[kurok_]所创，转载请带上原文链接，感谢
https://blog.csdn.net/Misaka_____/article/details/125692418