发布于2021-02-18
上次编辑2021-04-19
Wiki#
P/NP/NP-complete/NP-hard
- P 问题：可以在多项式时间内被解决的问题。
- NP 问题：可以在多项式时间内被验证其正确性的问题。
- NP 完全：
- 它是一个 NP 问题
- 其他属于 NP 的问题都可在多项式时间内归约成它
- NP 困难：所有 NP 问题都可以多项式时间归约到该问题
因为 NP 困难问题未必可以在多项式时间内验证一个解的正确性（即不一定是 NP 问题），因此即使 NP 完全问题有多项式时间的解（P = NP），NP 困难问题依然可能没有多项式时间的解。因此 NP 困难问题“至少与 NP 完全问题一样难”。
返回顶部
在手机上阅读