gpt4 book ai didi

algorithm - 是否存在不是 NP 完全或 P 的 NP 问题?

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:31:45 25 4
gpt4 key购买 nike

我试图理解 P、NP、NP-Complete 和 NP-Hard 之间的关系。

我相信我开始理解一般的想法,但是,我对这个问题挂断了(见标题)。

在 P 时间内不可解决、在 P 时间内可验证但不是 NP 完全问题的示例是什么?

如果我遗漏了一些理解,请填写。

提前致谢

最佳答案

如评论中所述,这是该问题的错误站点。不过,可以简单回答一下:

What is an example of a problem that is not solvable in P time, is verifiable in P time but is not NP-Complete?

如果我理解你,你想要的是 (1) 不在 P 中,(2) 不在 NP 中,(3) 不在 NPC 中的问题。这样的问题就是NP-中间(NPI)问题。

不知道有没有这样的问题,因为不知道P=NP.

如果P=NP那么显然不存在这样的问题;如果 P=NP 则 P=NPC,因此每个可以在 P 时间内验证的问题都在所有 P、NP 和 NPC 中,因为它们是相等的。

如果 P!=NP 则已知存在这样的问题;至少有一个存在。不幸的是,如果 P!=NP,我们不知道我们面临的任何现实世界问题是否在 NPI 中。可以在此处找到可能的候选人列表:

https://en.wikipedia.org/wiki/NP-intermediate

简而言之:知道 NPI 是否为空等同于解决 P!=NP 的证明,所以开始吧!如果你能找到一个绝对属于NP但绝对不属于P或NPC的问题,那么就有大奖等着你。

关于algorithm - 是否存在不是 NP 完全或 P 的 NP 问题?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48156484/

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