P*f
2 楼
who give some comments?
【在 s***e 的大作中提到】
: http://www.popyard.org/cgi-mod/npost.cgi?num=47325
【在 s***e 的大作中提到】
: http://www.popyard.org/cgi-mod/npost.cgi?num=47325
A*X
3 楼
non-sense
【在 P*****f 的大作中提到】
: who give some comments?
【在 P*****f 的大作中提到】
: who give some comments?
h*t
4 楼
我觉得引理一本身就是问题。如果该集合的元素有规律性，那么可以利用该
规律性更有效的判定。比如判断一个数是不是偶数，不一定需要做无穷步
比较，只要判断该数能否被2整除。
实际上很多计算机算法就是在发现并利用这些规律。 不然最短路也是要用
指数时间来计算了。
实际上引理一只说明，NP问题的最坏时间是指数的。并不说明没有更好时间的
算法。作者的根本概念有问题.
【在 P*****f 的大作中提到】
: who give some comments?
规律性更有效的判定。比如判断一个数是不是偶数，不一定需要做无穷步
比较，只要判断该数能否被2整除。
实际上很多计算机算法就是在发现并利用这些规律。 不然最短路也是要用
指数时间来计算了。
实际上引理一只说明，NP问题的最坏时间是指数的。并不说明没有更好时间的
算法。作者的根本概念有问题.
【在 P*****f 的大作中提到】
: who give some comments?
w*g
5 楼
lemma, He is not the smartest guy in the country.
proof, prove by contradiction,
if he is the smartest guy, his proof has already been published in
science.
theorem, Only one of the smartest guy can solve NP=P or NP!=P
corollory, He doesn't solve NP vs P problem.[A
【在 h****t 的大作中提到】
: 我觉得引理一本身就是问题。如果该集合的元素有规律性，那么可以利用该
: 规律性更有效的判定。比如判断一个数是不是偶数，不一定需要做无穷步
: 比较，只要判断该数能否被2整除。
: 实际上很多计算机算法就是在发现并利用这些规律。 不然最短路也是要用
: 指数时间来计算了。
: 实际上引理一只说明，NP问题的最坏时间是指数的。并不说明没有更好时间的
: 算法。作者的根本概念有问题.
proof, prove by contradiction,
if he is the smartest guy, his proof has already been published in
science.
theorem, Only one of the smartest guy can solve NP=P or NP!=P
corollory, He doesn't solve NP vs P problem.[A
【在 h****t 的大作中提到】
: 我觉得引理一本身就是问题。如果该集合的元素有规律性，那么可以利用该
: 规律性更有效的判定。比如判断一个数是不是偶数，不一定需要做无穷步
: 比较，只要判断该数能否被2整除。
: 实际上很多计算机算法就是在发现并利用这些规律。 不然最短路也是要用
: 指数时间来计算了。
: 实际上引理一只说明，NP问题的最坏时间是指数的。并不说明没有更好时间的
: 算法。作者的根本概念有问题.
f*e
6 楼
啊啊啊啊啊？？
“NP完全性问题是世界难题，实际上关于NP≠P的证明并不难，人们误解了它，它的证明
竟然如此简单明了，证明的主要部分已经向SIAM杂志与《计算机学报》，投稿。”
简单明了，ft...等SIAM收了再说吧
【在 s***e 的大作中提到】
: http://www.popyard.org/cgi-mod/npost.cgi?num=47325
“NP完全性问题是世界难题，实际上关于NP≠P的证明并不难，人们误解了它，它的证明
竟然如此简单明了，证明的主要部分已经向SIAM杂志与《计算机学报》，投稿。”
简单明了，ft...等SIAM收了再说吧
【在 s***e 的大作中提到】
: http://www.popyard.org/cgi-mod/npost.cgi?num=47325
c*m
7 楼
"power(2,n) 个元素的集合的属于判定问题是最简单的NP完全性问题"
这个对吗？
【在 s***e 的大作中提到】
: http://www.popyard.org/cgi-mod/npost.cgi?num=47325
这个对吗？
【在 s***e 的大作中提到】
: http://www.popyard.org/cgi-mod/npost.cgi?num=47325
b*g
8 楼
同是NP-complete问题,哪有什么难易之分?
除非是讨论其approximability
【在 c******m 的大作中提到】
: "power(2,n) 个元素的集合的属于判定问题是最简单的NP完全性问题"
: 这个对吗？
除非是讨论其approximability
【在 c******m 的大作中提到】
: "power(2,n) 个元素的集合的属于判定问题是最简单的NP完全性问题"
: 这个对吗？
s*t
9 楼
to discuss the complexity, the input size should be some *natural*
representation. It is well known that many NP-complete problem can indeed
be solved in polynomial time if some *innatural* representation is used.
For example, Knapsack problem is NP-complete. But it can be solved in
polynomial time
if the max objective is bound above by some value K, i.e., O(K ( poly(n) ).
Here, n
is the number of total available items.
【在 s***e 的大作中提到】
: http://www.popyard.org/cgi-mod/npost.cgi?num=47325
representation. It is well known that many NP-complete problem can indeed
be solved in polynomial time if some *innatural* representation is used.
For example, Knapsack problem is NP-complete. But it can be solved in
polynomial time
if the max objective is bound above by some value K, i.e., O(K ( poly(n) ).
Here, n
is the number of total available items.
【在 s***e 的大作中提到】
: http://www.popyard.org/cgi-mod/npost.cgi?num=47325
s*t
10 楼
i agree with your point.
【在 h****t 的大作中提到】
: 我觉得引理一本身就是问题。如果该集合的元素有规律性，那么可以利用该
: 规律性更有效的判定。比如判断一个数是不是偶数，不一定需要做无穷步
: 比较，只要判断该数能否被2整除。
: 实际上很多计算机算法就是在发现并利用这些规律。 不然最短路也是要用
: 指数时间来计算了。
: 实际上引理一只说明，NP问题的最坏时间是指数的。并不说明没有更好时间的
: 算法。作者的根本概念有问题.
【在 h****t 的大作中提到】
: 我觉得引理一本身就是问题。如果该集合的元素有规律性，那么可以利用该
: 规律性更有效的判定。比如判断一个数是不是偶数，不一定需要做无穷步
: 比较，只要判断该数能否被2整除。
: 实际上很多计算机算法就是在发现并利用这些规律。 不然最短路也是要用
: 指数时间来计算了。
: 实际上引理一只说明，NP问题的最坏时间是指数的。并不说明没有更好时间的
: 算法。作者的根本概念有问题.
P*f
11 楼
feel same here
【在 h****t 的大作中提到】
: 我觉得引理一本身就是问题。如果该集合的元素有规律性，那么可以利用该
: 规律性更有效的判定。比如判断一个数是不是偶数，不一定需要做无穷步
: 比较，只要判断该数能否被2整除。
: 实际上很多计算机算法就是在发现并利用这些规律。 不然最短路也是要用
: 指数时间来计算了。
: 实际上引理一只说明，NP问题的最坏时间是指数的。并不说明没有更好时间的
: 算法。作者的根本概念有问题.
h*t
12 楼
Actually I feel there is some sort of link between NP-completeness and
undecidability when I wrote down the example. I was using the set
of all even integers. A straightforward one-by-one comparison over
all even integers leads to a complexity beyond NP-completeness; it
leads to undecidability because the algorithm will not terminate
in the worst case. Now I'm curious whether we can exploit this to
align NP vs. P to undecidable vs. decidable. Maybe we can discuss
on this more.
【在 s***t 的大作中提到】
: i agree with your point.
undecidability when I wrote down the example. I was using the set
of all even integers. A straightforward one-by-one comparison over
all even integers leads to a complexity beyond NP-completeness; it
leads to undecidability because the algorithm will not terminate
in the worst case. Now I'm curious whether we can exploit this to
align NP vs. P to undecidable vs. decidable. Maybe we can discuss
on this more.
【在 s***t 的大作中提到】
: i agree with your point.
h*t
13 楼
Pls see the post above. We can discuss more if you are interested.
【在 P*****f 的大作中提到】
:
: feel same here
【在 P*****f 的大作中提到】
:
: feel same here
N*n
14 楼
民科
【在 s***e 的大作中提到】
: http://www.popyard.org/cgi-mod/npost.cgi?num=47325
【在 s***e 的大作中提到】
: http://www.popyard.org/cgi-mod/npost.cgi?num=47325
相关阅读
帮版主版副宣布一下：本版随便PAupdate on Niu Ren ..各位DB领域的兄弟,有谁了解nick koudas?Siggraph results are out !!!这个会议是什么等级的啊?Bioinformatics现在怎么样？How do you all think about UMASS?[转载]Computer Science Research到了最危险的时刻nornal time to graduate for cs major?Database faculty好找吗？软工家谱Anyone doing research on multi-agent sys[转载] Help, What is .umt file?Re: networking is firstWisc CS is really small ..[转载] How to minimize this variance?博士毕业直接去UIUC EECS做faculty...ACM's action on plagiarism说几句Re: 靠！Re: [转载] Re: 【转帖】今年找学校faculty的工作就这么难嘛