s***e
发帖数: 1490 | |
P*****f
发帖数: 2272 | |
A*X
发帖数: 908 | 3 non-sense
【在 P*****f 的大作中提到】
: who give some comments?
|
h****t
发帖数: 93 | 4 我觉得引理一本身就是问题。如果该集合的元素有规律性，那么可以利用该
规律性更有效的判定。比如判断一个数是不是偶数，不一定需要做无穷步
比较，只要判断该数能否被2整除。
实际上很多计算机算法就是在发现并利用这些规律。 不然最短路也是要用
指数时间来计算了。
实际上引理一只说明，NP问题的最坏时间是指数的。并不说明没有更好时间的
算法。作者的根本概念有问题.
【在 P*****f 的大作中提到】
: who give some comments?
|
w*******g
发帖数: 9932 | 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问题的最坏时间是指数的。并不说明没有更好时间的
: 算法。作者的根本概念有问题.
|
f**e
发帖数: 1269 | 6 啊啊啊啊啊？？
“NP完全性问题是世界难题，实际上关于NP≠P的证明并不难，人们误解了它，它的证明
竟然如此简单明了，证明的主要部分已经向SIAM杂志与《计算机学报》，投稿。”
简单明了，ft...等SIAM收了再说吧
【在 s***e 的大作中提到】
: http://www.popyard.org/cgi-mod/npost.cgi?num=47325
|
c******m
发帖数: 98 | 7 "power(2,n) 个元素的集合的属于判定问题是最简单的NP完全性问题"
这个对吗？
【在 s***e 的大作中提到】
: http://www.popyard.org/cgi-mod/npost.cgi?num=47325
|
b**g
发帖数: 335 | 8 同是NP-complete问题,哪有什么难易之分?
除非是讨论其approximability
【在 c******m 的大作中提到】
: "power(2,n) 个元素的集合的属于判定问题是最简单的NP完全性问题"
: 这个对吗？
|
s***t
发帖数: 113 | 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
|
s***t
发帖数: 113 | 10 i agree with your point.
【在 h****t 的大作中提到】
: 我觉得引理一本身就是问题。如果该集合的元素有规律性，那么可以利用该
: 规律性更有效的判定。比如判断一个数是不是偶数，不一定需要做无穷步
: 比较，只要判断该数能否被2整除。
: 实际上很多计算机算法就是在发现并利用这些规律。 不然最短路也是要用
: 指数时间来计算了。
: 实际上引理一只说明，NP问题的最坏时间是指数的。并不说明没有更好时间的
: 算法。作者的根本概念有问题.
|
P*****f
发帖数: 2272 | 11
feel same here
【在 h****t 的大作中提到】
: 我觉得引理一本身就是问题。如果该集合的元素有规律性，那么可以利用该
: 规律性更有效的判定。比如判断一个数是不是偶数，不一定需要做无穷步
: 比较，只要判断该数能否被2整除。
: 实际上很多计算机算法就是在发现并利用这些规律。 不然最短路也是要用
: 指数时间来计算了。
: 实际上引理一只说明，NP问题的最坏时间是指数的。并不说明没有更好时间的
: 算法。作者的根本概念有问题.
|
h****t
发帖数: 93 | 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.
|
h****t
发帖数: 93 | 13 Pls see the post above. We can discuss more if you are interested.
【在 P*****f 的大作中提到】
:
: feel same here
|
N********n
发帖数: 8363 | |
