P = NP的问题可能是所有计算机科学中最着名的问题.这是什么意思？为什么它如此有趣？
哦,为了额外的功劳,请发表声明的真相或虚假证明.:)
根据我的理解,所有NP完全问题都是NP难的,但已知一些NP难问题不是NP完全的,NP难问题至少与NP完全问题一样难.
这是否意味着非NP完全的NP难问题更难？它是如何变得更难？
真的......我本周二正在进行最后一次毕业考试,这是我无法理解的事情之一.我意识到NP问题的解决方案可以在多项式时间内得到验证.但决定论与此有何关系？
如果你能解释我NP-complete和NP-hard得到他们的名字的地方,那就太棒了(我很确定我得到了他们的意思,我只是看不出他们的名字与他们的名字有什么关系是).
对不起,如果这是微不足道的,我似乎无法得到它( - :
谢谢大家!
它是一个特定NP完全问题的多项式时间算法,还是仅仅是抽象推理能够证明存在NP完全问题的解决方案？
似乎特定的算法更有帮助.有了它,我们要多方面地解决NP问题所需要做的就是将它转换成证明有解决方案的特定NP完全问题,我们就完成了.
我试图恢复密码.考虑到这一点,我认识到"密码恢复"这个问题是NP问题的一个很好的例子.如果您知道密码,则很容易在多项式时间内验证密码.但是如果您不知道密码,则必须在整个空间内搜索可能显示为指数时间的可能解决方案.
现在我的问题是:这不是证明P!= NP,因为"密码恢复"是NP的一个元素,可以显示需要多于多项式时间来运行？
我知道,P = NP一直没有解决到现在,但有谁能够告诉我一些关于以下内容:当前什么是最有前途的数学/计算机科学的方法是可以有助于解决这个问题？或者到目前为止还没有任何已知的方法可能有用吗？是否有关于此主题的任何(免费)纲要,我可以在这个领域找到所有/大部分研究成果？
有一个工具称FindBugs它可以检测给定程序/代码库中的无限永不停止循环.
这意味着FindBugs可以通过分析代码来检测程序是否结束.暂停问题是定义以下问题:
给定任意计算机程序的描述,确定程序是否完成运行或继续运行
那么这是否意味着停止问题得到解决或停止问题的一部分得到解决？
我阅读了维基百科上的文章,但无法理解究竟是什么NP问题.任何人都可以告诉我他们以及他们与P问题的关系是什么？
我很困惑,经过一番阅读后,这是我的想法:
P在NP中,NP在NP完全中.因此,所有P都可以在NP和NP-Complete中？
这是否意味着存在可以是NP和NP-Complete的排序算法？
希望这听起来不是太愚蠢.
我正在学习P和NP.
我已经读过,确定给定数字是否为素数的问题是P中的一个问题,这意味着它有一个多项式时间算法来解决它.
我还读到这个事实在2002年被证明是AKS的算法.
众所周知,我们可以通过运行直到其平方根来确定特定数字是否为素数.
伪代码:
isPrime(N):
sqrt(N) <- squareRoot(N)
for i from 2 to Sqrt(N)
if (n mod i == 0)
return false
return true
我的问题很简单:
为什么上面的算法不能证明这个问题在P？
谢谢 :)
我在可满足和不可满足子句文件的 cnf 文件中看到了一些错误SATLIB 基准问题
更具体地说，我发现这里的 zip 文件夹的第一个文件： 20 个变量，91 个子句 - 1000 个实例，所有可满足的 包含一个标题为“uf20-01”的文件，其方程显然是不可满足的第 15 行的第 7 个子句和第 4 行的第 87 个子句彼此完全相反！((5 19 17) 和 (-5 -19 -17))
因此，在任何时间点对它们进行 AND 运算都会导致方程无法满足。
我得出的结论是，如果两个子句彼此完全相反，那么只有当方程不可满足时，否则方程是可满足的。我已经尝试了上述链接的另一个 UNSAT 文件，并进行了反复试验，尽管 MINISAT浏览器版本还说相同的文件不满意我已经找到了每个变量的 1 和 0 相同的解决方案。
上面的算法是我发布到期刊上的，但被拒绝了。
我的问题是：有人能给我一个不可满足的 3SAT 方程的例子吗？该方程仅包含 3 个变量（或者可能更多......），而没有任何子句与另一个子句完全相反？
如果我能得到这样的子句，那么算法就是错误的（但它仍然证明许多 SAT 基准问题是 UNSAT），并且不能证明第一个链接中的许多 UNSAT 问题确实是 SAT。
这是在逗我的心，希望大家能理解，如果上面的算法是对的，那么我就证明了P=NP！它也可以引发一场革命..
顺便说一句：我也已向 SATLIB 联系人发送了电子邮件，但 2 天后仍然没有回复有关第二个链接文件的信息。