标签: np

是否存在确定性算法来检查图形是否包含从源到目的地的顶点不相交路径,具有复杂性O(nm^2)(n是顶点数,m是边数)或者是NP-Hard(如果是,为什么)？顶点不相交路径表示没有共同内部顶点的路径.例如.

s -> a -> b -> c -> d  
s -> x -> y -> z -> d

顶点不相交但是

s -> a -> b -> c -> d
s -> x -> a -> z -> d
          ^

不是因为a是常见的顶点.

完整的问题是:

我试图了解这些语言类别之间的关系。有人可以按照我的想法排序吗？例如，如果我采用语言 HAMPATH = {: G has a hamiltonion path}。我知道这是 NP 和 NP 难。这是否教会了我关于 R、RE 核心的任何信息？它们之间有什么联系吗？

我在网上看到，求最长路径问题是NP完全问题。

出于某种原因，我的老师告诉我这不是一个 NP 完全问题。所以现在我正在寻找一个示例，该示例显示获得最长路径所需的计算量大于多项式时间。

目前，我只看到了具有多项式复杂度时间的例子。

任何人都可以给我证明这个问题是NP完全的吗？

我正在研究 NP 完备性，我对 NP 问题的定义有疑问。

材料说

不确定性是指可以在 O(1) 时间内从多项式多个选项中猜测出解决方案

这里，什么意思polynomially many options in O(1) time？

例如，对于著名3SAT问题，选项不是呈指数级增长吗？
（bc 每个文字都可以是trueorfalse并且如果有 n 个文字，则选项总数为2*2*2* ... * 2 = 2^n）

然而，它说3SAT问题是NP问题。证书数量呈指数级增长，怎么可能是NP问题呢？

谢谢

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

我相信我开始理解一般的想法但是,我对这个问题感到困惑(见标题).

什么是这是一个问题的例子并不 P中时间内可解,是在P个时间核查的,但不是 NP完全？

如果我缺少一些理解,请填写我.

提前致谢