【NP】规约与问题复杂度

发布时间：2024年01月04日

目录

多项式时间规约

Polynomial-Time Reductions ：如果问题 Y Y Y 的任意实例可以通过多项式次数的标准计算步骤，加上对解决问题 X X X 的黑盒的多项式次数调用来解决，那么称问题 Y Y Y 可以在多项式时间归约为问题 X X X，记为 Y ≤ p X Y\le_p X Y≤p?X 。

在这里插入图片描述
规约的两个用途：假设 Y ≤ p X Y\le_p X Y≤p?X

  • 设计算法、证明下界：如果 X X X 可以在多项式时间内求解，那么 Y Y Y 也可以在多项式时间内求解
  • 确定问题之间的相对难度：如果在多项式时间内无法求解 Y Y Y ，那么 X X X 也不能在多项式时间内求解

复杂度类

判定问题：输出是布尔值（是/否）的问题

复杂类性质
P可以在多项式时间内解决的判定问题
NP有如下性质的判定问题：如果答案为 是 ，可以在多项式时间内检查该答案的正确性
co-NP有如下性质的判定问题：如果答案为 否 ，可以在多项式时间内检查该答案的正确性
NP-hard问题 π \pi π 可以在多项式时间内解决，那么 π ∈ \pi \in π∈ NP-hard
NP-complete问题 π ∈ \pi \in π∈ NP 并且 π ∈ \pi\in π∈ NP-hard , 那么 π ∈ \pi \in π∈ NP-complete

常见复杂度类之间的关系

  • P 中的每?个问题都在 NP 中
  • P 中的每?个问题都在 co-NP 中
  • P ≠ NP ∩ co-NP

在这里插入图片描述

文章来源:https://blog.csdn.net/cold_code486/article/details/135363904
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
最新文章