天道酬勤,学无止境

p-np

A 到 B 的减少:对或错(Reduction of A to B : True or False)

问题 有两种说法:如果决策问题 A 是多项式时间可归约到决策问题 B(即A≤ pB ),并且 B 是 NP 完全的,则 A 必须是 NP 完全的。 和: 如果决策问题 B 可以多项式时间简化为决策问题 A(即B≤ pA ),并且 B 是 NP 完全的,则 A 必须是 NP 完全的。 以上哪些说法是正确的? 你也能解释一下吗? 回答1 第一个陈述是错误的,因为这意味着通过解决 B 然后应用一些多项式时间算法你可以解决 A 但也许有另一种解决 A 的方法不需要解决 B 并且可能只是多项式。 第二个陈述是正确的,因为这意味着您可以通过先求解 A 然后应用一些多项式时间算法来求解 B 但 B 是 NP 完全的,所以 A 必须是 NP 完全的

2021-10-19 00:31:23    分类:技术分享    algorithm   computation   p-np

Reduction of A to B : True or False

There are two statements: If a decision problem A is polynomial-time reducible to a decision problem B (i.e., A≤ pB ), and B is NP-complete, then A must be NP-complete. And: If a decision problem B is polynomial-time reducible to a decision problem A (i.e., B≤ pA ), and B is NP-complete, then A must be NP-complete. Which of the above statements are true? Can you also give explanation?

2021-10-18 14:27:10    分类:问答    algorithm   computation   p-np

What are NP problems?

I read the article on wikipedia but could not understand what exactly are NP problems. Can anyone tell me about them and also what is relation of them with P Problems?

2021-07-30 11:13:46    分类:问答    complexity-theory   p-np

解释 Vinay Deolalikar 证明 P != NP [关闭](Explain the proof by Vinay Deolalikar that P != NP [closed])

问题 关闭。 此问题不符合 Stack Overflow 准则。 它目前不接受答案。 想改善这个问题吗? 更新问题,使其成为 Stack Overflow 的主题。 4年前关闭。 改进这个问题 最近,惠普实验室的 Vinay Deolalikar 发表了一篇论文,声称已经证明 P != NP。 有人能解释一下这个证明如何适用于我们不太喜欢数学的人吗? 回答1 我只是浏览了这篇论文,但这里有一个关于它是如何结合在一起的粗略总结。 来自论文的第 86 页。 ...多项式时间算法成功地将问题连续“分解”为更小的子问题,这些子问题通过条件独立性相互连接。 因此,多项式时间算法无法解决其顺序与基础问题实例相同的块需要同时解决的情况下的问题。 论文的其他部分表明某些 NP 问题不能以这种方式分解。 因此 NP/= P 这篇论文的大部分内容都用于定义条件独立性并证明这两点。 回答2 Dick Lipton 有一篇关于该论文及其第一印象的不错的博客条目。 不幸的是,这也是技术性的。 据我了解,Deolalikar 的主要创新似乎是使用了统计物理学和有限模型理论中的一些概念,并将它们与问题联系起来。 我和 Rex M 在一起,有些结果,主要是数学结果,无法向缺乏技术掌握的人表达。 回答3 我喜欢这个(http://www.newscientist.com/article/dn19287-p--np

2021-06-23 07:56:25    分类:技术分享    math   computer-science   complexity-theory   proof   p-np

Explain the proof by Vinay Deolalikar that P != NP [closed]

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers. Want to improve this question? Update the question so it's on-topic for Stack Overflow. Closed 4 years ago. Improve this question Recently there has been a paper floating around by Vinay Deolalikar at HP Labs which claims to have proved that P != NP. Could someone explain how this proof works for us less mathematically inclined people?

2021-05-15 05:59:05    分类:问答    math   computer-science   complexity-theory   proof   p-np

NP问题为什么这样称呼(以及NP难题和NP难题)?(Why are NP problems called that way (and NP-hard and NP-complete)?)

问题 真的。。我本星期二要进行最后的毕业考试,而那是我永远无法理解的事情之一。 我意识到可以在多项式时间内验证NP问题的解决方案。 但是,确定性与这有什么关系呢? 而且,如果您能向我解释NP完整和NP困难在何处获得他们的名字,那将是很棒的(我敢肯定,我明白了他们的意思,我只是不知道他们的名字与他们的名字有什么关系是)。 抱歉,这很琐碎,我似乎无法理解(-: 谢谢大家! 回答1 P 确定性图灵机可以在多项式时间内解决的所有问题。 例如 一类非确定性图灵机可以在多项式时间内解决的所有问题(也可以由一确定性图灵机在多项式时间内进行验证)。 NP-硬 一类问题,“至少与NP中最困难的问题一样困难”。 形式上,问题在于NP-Hard,如果存在一个NP-完全问题,该问题可以通过多项式时间Turing减少; (另请参见:如果可以通过带有问题的oracle的oracle机器在多项式时间内解决该问题)。 这个名字的来历很明显。 人大 NP和NP-Hard都是这类问题。 关于命名,甚至维基百科都不确定为什么要这样命名。 回答2 让我们从“不确定性”开始。 确定性机器一次可以处于一种状态。 我们实际上可以制造它们。 非确定性机器是一种理论构造,可以一次处于多个状态。 (这里与量子计算有相似之处,但出于我们的目的,它们具有误导性。请忽略它们。) 如果我们想用确定性机器解决问题,则将其启动

2021-05-09 06:08:27    分类:技术分享    computer-science   complexity-theory   p-np

“Finding all the code in a given binary is equivalent to the Halting problem.” Really?

Was just reading the highly voted question regarding Emulators and the statement It's been proven that finding all the code in a given binary is equivalent to the Halting problem. Really stuck out at me. Surely that can't be true? Isn't it just a large dependency graph? Would be really grateful for some further insight into this statement.

2021-04-27 21:50:07    分类:问答    computer-science   emulation   halting-problem   p-np

什么是“ P = NP?”,为什么它是一个如此著名的问题? [关闭](What's “P=NP?”, and why is it such a famous question? [closed])

问题 关闭。 这个问题是题外话。 它当前不接受答案。 想要改善这个问题吗? 更新问题,使它成为Stack Overflow的主题。 8年前关闭。 改善这个问题 在计算机科学中,P = NP是否可能是最著名的问题。 这是什么意思? 为何如此有趣? 哦,为了获得额外的荣誉,请张贴有关该陈述的真实性或虚假性的证明。 :) 回答1 P代表多项式时间。 NP代表不确定的多项式时间。 定义: 多项式时间意味着算法的复杂度为O(n ^ k),其中n是数据的大小(例如,要排序的列表中元素的数量),而k是常数。 复杂度是根据将要执行的操作数来衡量的时间,它是数据项数量的函数。 操作是任何有意义的,因为对于一个特定的任务的基本操作。 对于排序,基本操作是一个比较。 对于矩阵乘法,基本运算是两个数相乘。 现在的问题是,确定性与非确定性是什么意思? 有一个抽象的计算模型,一个称为图灵机(TM)的假想计算机。 该机器具有有限数量的状态和无限的磁带,磁带具有离散的单元,可以在其中写入和读取有限的一组符号。 在任何给定时间,TM处于其状态之一,并且它正在查看磁带上的特定单元。 根据从该单元读取的内容,它可以在该单元中写入一个新符号,将磁带向前或向后移动一个单元,然后进入另一种状态。 这称为状态转换。 令人惊讶的是,通过精心构造状态和转换,您可以设计一个TM,它等效于任何可以编写的计算机程序。

2021-04-20 16:50:45    分类:技术分享    computer-science   theory   complexity-theory   np-complete   p-np

Why are NP problems called that way (and NP-hard and NP-complete)?

Really.. I'm having the last test for graduation this Tuesday, and that's one of the things I just never could understand. I realize that a solution for NP problem can be verfied in polynomial time. But what does determinism has to do with that? And if you could explain me where NP-complete and NP-hard got their names, that would be great (I'm pretty sure I get the meaning of them, I just don't see what their names have to do with what they are). Sorry if that's trivial, I just can't seem to get it (-: Thanks all!

2021-04-15 03:20:36    分类:问答    computer-science   complexity-theory   p-np

What's “P=NP?”, and why is it such a famous question? [closed]

Closed. This question is off-topic. It is not currently accepting answers. Want to improve this question? Update the question so it's on-topic for Stack Overflow. Closed 8 years ago. Improve this question The question of whether P=NP is perhaps the most famous in all of Computer Science. What does it mean? And why is it so interesting? Oh, and for extra credit, please post a proof of the statement's truth or falsehood. :)

2021-04-07 20:03:04    分类:问答    computer-science   theory   complexity-theory   np-complete   p-np