问题标签 [np]

我不是要求一种算法来检查图中是否存在负循环（Bellman Ford 或 Floyd Warshall 可以做到这一点），而是是否存在一个多项式时间算法来找到两点之间的最短路径图包含至少一个从源顶点可到达的负循环，并且可以从负循环到达目标顶点。

CLIQUE 问题——在图中找到最大团的问题是 NP 完全的。也就是说，CLIQUE 是

a.) 在 NP 和 b.) 中存在一个 NP 完全问题，一个 3-SAT，在多项式时间内简化为 CLIQUE。

上面的（b）部分很好——在每一个资源中都有，而且解释得很好。对于 (a) 部分，据我所知，我们需要具备以下条件：给定一个特定的解决方案实例，我们需要证明可以在多项式时间内验证该解决方案是该问题的答案。因此，例如，给定一个特定的图和它的子图，我们应该能够检查该子图是否是该图中最大尺寸的集团。

到目前为止，我阅读的资源将这部分 (a) 表述为“简单、直接等”或“可以在 O(n^2) 时间内显示给定子图是一个集团/不是”。但是，这里的验证不仅仅是它是否是一个团，而是它是否是图中的一个最大团。这如何在多项式时间内决定？

我在这里想念什么？

我见过几个地方简单地指出已知 P 是 NP 和 co-NP 的交集的一个子集。证明 P 是 NP 的子集的证明并不难找到。所以为了证明它是交集的一个子集，剩下要做的就是证明 P 是 co-NP 的一个子集。这可能是什么证据？非常感谢！

根据wiki，它将需要（N-1）！计算 N 个城市的旅行。我找到了一种更好的方法，但我无法通过数学计算我改进了多少。我可以告诉你，在我的家用电脑上，我能够在不到 1 小时的时间内解决 20 个城市的地图。20！= 2.43290200e+18。这是我所做的：

当使用 brout 算法搜索 N 个城市的路线（让它们命名：City(1)、City(2)、City(3)...City(N)）时，您将首先执行此测试：City( 1), City(2), City(3), City(4)... City(N) 一段时间后，这个：City(1), City(3), City(2), City(4 )... 城市 (N)。我声称第二次计算是不必要的。如果我只计算一次 City(4) ... City(N) 的最短路线，我可以将其用于第二次计算并确定哪条路线更好。

使用这个技巧，我可以通过以下方式减少我为 K 城市所做的计算次数： (N - k) 这是我可以选择的第一个城市的选项数量，乘以 (N - K - 1) ！这是我必须选择其余城市的选项数量，减去第一次，我需要执行完整计算。所以它将是（N - K）！。您需要对从 k = 3 到 k = N - 2 的所有 K 求和。

这是我所到之处，（不远）......我希望你能帮我计算一下。

我有个问题。我认为这是一个 NP 难题，但我不确定。首先，让我描述一下空间；

假设我有这些事件a,b,c,d,e,f，请考虑从这些事件生成的 3 长度有序序列的所有可能性。喜欢，

顺序对序列很重要，因此总共将有 120 个 3 长度序列（6 个事件的排列）。此外，所有这些 3 长度的序列都将是 0 到 1 之间的值。

现在考虑一个 6 长度的序列。

的值seq可以确定为对 中的所有 3 长度序列求和seq。

seq可以通过从任意 3 个事件中找到所有 3 长度序列，seq而无需更改其顺序。其中的一些例子；

问题是;

我需要在所有可能的 6 长度序列中找到一个具有最小（或最大）值的 6 长度序列。您可以猜到，这只是一个简单的示例。我需要在有 20-100 个事件的最大空间上工作。因此，生成所有 6 长度序列空间不是解决方案。

我知道很难找到最小（或最大），因此找到一个值接近最小（或最大）的序列也是可以接受的。如果您能建议我可以在 Python 上实现的算法或方法，我将不胜感激。

谢谢，

我知道您不能提供验证证书。但是，我只是在想，为什么我们不能将输入提供给决定 SAT 的 NDTM，然后反转答案？缺陷在哪里？

你们中的任何人都知道一种解决方案，即使是针对旅行推销员问题的平庸解决方案。我有 3 个人打算访问 31 个目的地……我不知道该怎么办？

谢谢大家 -

格言

我知道我们可以将 FPTAS 应用于像 0-1 背包这样的弱 NP 问题。

但是为什么我们不能将相同的原则应用于像装箱这样的强 NP 问题。我也检查了 wiki 页面，但理解得很少。

一些 NP 难的问题也是固定参数可处理的，或 FPT。如果有一种算法可以在时间 f(k) · |x| 中解决问题，维基百科将问题描述为可处理的固定参数 ^O(1)。

这是什么意思？为什么这个概念有用？

如果有人能够证明 NP 完全问题的指数下限，那会证明 P ≠ NP 吗？