gpt4 book ai didi

computer-science - 所有的 NP 问题都是 NP 完全的吗?

转载 作者:行者123 更新时间:2023-12-03 23:39:10 24 4
gpt4 key购买 nike

NP-完全的定义是

一个问题是 NP 完全的,如果

  • 它属于 NP 类
  • NP 多项式中的所有其他问题都转化为它

  • 那么,如果 NP 中的所有其他问题都转化为一个 NP-完全问题,那么这不也意味着所有 NP 问题也是 NP-完全问题吗?如果两者相同,将两者分类有什么意义?

    换句话说,如果我们有一个 NP 问题,那么通过(2)这个问题可以转化为一个 NP 完全问题。因此,NP 问题现在是 NP-完全的,并且 NP = NP-完全。两个类是等价的。

    只是想为自己澄清这一点。

    最佳答案

    Are all NP problems also NP-complete?



    Only if P = NP.

    enter image description here

    关于computer-science - 所有的 NP 问题都是 NP 完全的吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7367537/

    24 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com