问题标签 [p-np]

我正在参加关于复杂性和解决问题的 400 级课程。最后一个项目是实现一个与 P 和 NP 相关的问题。不幸的是，老师对项目的界限一直含糊不清。

所以我只是想我会在这里询问是否有人对我可能实施的中等难度问题提出建议。我知道这个问题很模糊，但我很想知道是否有人有最喜欢的问题。

谢谢！

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

有一个工具叫做FindBugs它可以检测给定程序/代码库中的无限循环。

这意味着FindBugs可以通过分析代码来检测程序是否会结束。停止问题是定义以下问题的问题：

给定任意计算机程序的描述，决定程序是完成运行还是永远继续运行

那么这是否意味着停止问题已解决或停止问题的子集已解决？

我正在尝试比较每种 SolvePnP 可能性之间的精度和耗时：CV_ITERATIVE、CV_EPNP 和 CV_P3P

我还将我的结果与 Matlab EPNP 进行了比较。

看起来 EPNP 和 P3P 失败了：

给我吗 ：

迭代：旋转矩阵：[1，-2.196885546074445e-016，9.692430825310778e-016；2.196885546074445e-016, 1, 1.012059558506939e-015; -9.692430825310778e-016, -1.012059558506939e-015, 1]

迭代：翻译向量：[71.42857142857143；-151.4285714285714；500]

P3P：旋转矩阵：[1, 0, 0; 0, 1, 0; 0, 0, 1]

P3P：翻译向量：[-3.97771428571427e-015; -4.022285714285698e-015；9.989999999999962e-017]

EPNP：旋转矩阵：[1, 0, 0; 0, 1, 0; 0, 0, 1]

EPNP：翻译向量：[-3.97771428571427e-015；-4.022285714285698e-015；9.989999999999962e-017]

有什么建议吗？

亚历山大·科恩曼

我正在学习P和NP。
我读过确定给定数字是否为素数的问题是 P 中的一个问题，这意味着它具有解决它的多项式时间算法。
我还读到这一事实在 2002 年被 AKS 算法证明。

众所周知，我们可以通过运行直到其平方根来确定特定数字是否为素数。

伪代码：

我的问题很简单：
为什么上面的算法不能证明这个问题在 P 中？
谢谢 ：）

我在可满足和不可满足子句文件的 cnf 文件中看到了一些错误SATLIB Benchmark Problems

更具体地说，我发现这里 zip 文件夹的第一个文件： 20 个变量，91 个子句 - 1000 个实例，所有可满足 包含一个标题为“uf20-01”的文件，其等式显然无法满足第 15 行的第 7 个子句和第 4 行的第 87 个子句完全相反！((5 19 17) 和 (-5 -19 -17))

因此，在任何时间点都有它们的 AND 运算将导致方程不可满足。

我得出的结论是，如果两个子句彼此完全相反，那么只有这个方程是不可满足的，否则这个方程是可满足的。浏览器版本还说相同的文件不满意我已经为每个变量找到了相同的 1 和 0 的解决方案。

上面的算法被我发布到期刊上，但被拒绝了。

我的问题是：有人可以给我一个无法满足的 3SAT 方程的例子，它只包含 3 个变量（或者可能更多......）而没有任何子句与另一个完全相反？

如果我能得到这样的条款，那么算法是错误的（但它仍然证明许多 SAT 基准问题是 UNSAT）并且它不会证明第一个链接中的许多 UNSAT 问题确实是 SAT。

这是在逗我，希望大家能看懂，好像上面的算法是对的，那我证明了P=NP！它也可以引发一场革命。

顺便说一句：我也已向 SATLIB 联系人发送了电子邮件，但 2 天后仍然没有关于第二个链接文件的回复。

我正在搜索图形着色算法，并且我找到了algorithm，作者陈述的算法是在多项式时间内运行的。作者还给出了C++程序源代码和演示程序。

可疑之处在于，图是否为 k 可着色的决策问题是 NP 完全的，因此在 P=NP 之前不应该存在多项式时间算法。

但是，作者并没有声称该算法适用于所有图，他只是说，他没有找到任何算法不适用于该图。

所以，问题是：该算法是否真的适用于每个图，这实际上意味着 P = NP，还是存在某些不适用的图/图类？或者也许只是复杂性计算中的错误？

我想到了一种通过以下方法解决 3SAT 问题的算法：

1）取cnf方程中至少有一个共同变量的所有子句。找到所有这些组合并将它们放入名为“Intersection”的列表中。列表“Intersection”现在包含相交子句组。

2）接下来，我们将特定组“Intersection”中的所有子句转换为 DNF。由于至少有一个共同变量，我认为它不会在指数时间内出现。

3）接下来，我们将所有获得的 DNF 转换为单个 DNF，因为它们在原始方程中都用 AND 门分隔。

4) 如果得到的 DNF 中有一个子句，则方程是可满足的，否则方程是不可满足的。这是因为不相交的子句（没有任何共同变量的子句）不会影响整个方程，最后如果我们与获得的 DNF 进行“与”，它只会将变量相乘并添加到现有的条款（如果有的话）。

我的问题是：

该算法的运行时间是多少，这是否证明了与 P=NP 相关的任何事情，因为我认为该算法非常有效。我之前的算法被其他人失望了，所以这次请花点时间分析算法，因为这是我的努力。

有两个陈述：如果决策问题 A 是多项式时间可简化为决策问题 B（即A≤ pB），并且 B 是 NP 完全的，则 A 必须是 NP 完全的。

和：

如果决策问题 B 是多项式时间可简化为决策问题 A（即B≤ pA），并且 B 是 NP 完全的，则 A 必须是 NP 完全的。

以上哪些说法是正确的？

也能解释一下吗？

我试图理解 NP Complete 的正式定义并且有一些问题。我想知道是否有人可以提供更多见解。

Jon Kleinberg 算法书说，如果每个 NP 问题都可以简化为问题 X，那么问题 X 在集合 NP Complete 中。

现在由于 P 是 NP 的子集，因此我们可以在多项式时间内将 P 中的任何问题简化为 NP 完全问题。这导致了一个矛盾，因为减少是在多项式时间内，我们可以在多项式时间内解决这个 NP 完全问题。这不可能是真的。所以我不确定这个推理在哪里是错误的。

此外，如果我们能够将多项式时间内的任何 NP 问题简化为 NP Complete，那么为什么我们说 NP Complete 更难。由于减少是多项式时间，渐近地说，它不应该有所作为。