I*****y
发帖数: 854 | 1 【 以下文字转载自 ChinaNews 讨论区 】
发信人: suite (suite), 信区: ChinaNews
标 题: 复旦20岁本科生证明世界级猜想 十余年来未解决
发信站: BBS 未名空间站 (Mon Jun 22 02:41:14 2009, 美东)
晚报讯 复旦大学昨天传来消息，该校计算机学院大三学生郭泽宇关于最小曼哈顿网络
问题的论文被美国ACM学会主办的第25届计算几何国际会议录用，文章同时作为最佳论
文之一被邀请投稿到会议特刊(DCG)。
这意味着计算几何领域十余年来未决的重要猜想被这位年仅20岁的本科生成功解决。
最小曼哈顿网络问题是计算机学院朱洪教授给自己指导的本科生们所开设的题目，
在城市规划、网络路由、大规模集成电路设计以及计算生物学等众多领域有着很好的应
用。记者张骞 (来源：新闻晚报)
(责任编辑：杨笑) |
J*****n
发帖数: 4859 | |
m****n
发帖数: 142 | 3 靠！这就叫“成功解决十余年来未解决世界级猜想”？！记者脑残啊？
我的理解是：如果他的结果是对的，是对现有的算法提高了一些近似度，离“成功解决
”远得不是一点半点。
当然，考虑到是本科生，还是要大加赞赏，值得嘉奖，前提是这个结果是正确的，呵呵
。 |
H*********r
发帖数: 659 | 4 I don't blame 记者, understanding exact/approximate solution is really
beyond their ken.
The professor/the student should't exaggerate the importance of their work.
【在 m****n 的大作中提到】
: 靠！这就叫“成功解决十余年来未解决世界级猜想”？！记者脑残啊？
: 我的理解是：如果他的结果是对的，是对现有的算法提高了一些近似度，离“成功解决
: ”远得不是一点半点。
: 当然，考虑到是本科生，还是要大加赞赏，值得嘉奖，前提是这个结果是正确的，呵呵
: 。
|
l******e
发帖数: 470 | 5 你也不是内行就别瞎理解了
你可以argue问题是不是“世界级”的，但是人家就是证明了个结论，证明了就是证明
了，没证明就是没证明。不是什么算法改进啊，提高近似度的。从这个问题是不是被证
明了的角度，问题就是成功解决了。
【在 m****n 的大作中提到】
: 靠！这就叫“成功解决十余年来未解决世界级猜想”？！记者脑残啊？
: 我的理解是：如果他的结果是对的，是对现有的算法提高了一些近似度，离“成功解决
: ”远得不是一点半点。
: 当然，考虑到是本科生，还是要大加赞赏，值得嘉奖，前提是这个结果是正确的，呵呵
: 。
|
H*********r
发帖数: 659 | 6 can anyone post his paper or abstract here?
【在 l******e 的大作中提到】
: 你也不是内行就别瞎理解了
: 你可以argue问题是不是“世界级”的，但是人家就是证明了个结论，证明了就是证明
: 了，没证明就是没证明。不是什么算法改进啊，提高近似度的。从这个问题是不是被证
: 明了的角度，问题就是成功解决了。
|
r******o
发帖数: 122 | 7 http://portal.acm.org/citation.cfm?id=1542362.1542429
【在 H*********r 的大作中提到】
: can anyone post his paper or abstract here?
|
L*****s
发帖数: 24744 | |
J*****n
发帖数: 4859 | 9
酸个屁，哈密尔顿问题本来就是NP，没有人会关心其复杂度。
每一个大牛的成功背后都有着别人看不到的努力，每一个定理的证明都凝聚着前人不可
或缺的基石。世界级猜想，敢碰都算是了不起的人物了。一个20岁的本科生就能解决，
你以为这还是欧拉时代么？
【在 L*****s 的大作中提到】
: 我看到有人想吃酸葡萄了..
|
S******y
发帖数: 72 | 10 彪悍。
【在 J*****n 的大作中提到】
:
: 酸个屁，哈密尔顿问题本来就是NP，没有人会关心其复杂度。
: 每一个大牛的成功背后都有着别人看不到的努力，每一个定理的证明都凝聚着前人不可
: 或缺的基石。世界级猜想，敢碰都算是了不起的人物了。一个20岁的本科生就能解决，
: 你以为这还是欧拉时代么？
|
|
|
l******e
发帖数: 470 | 11 同学拜托搞清楚哈密顿和曼哈顿的区别
【在 J*****n 的大作中提到】
:
: 酸个屁，哈密尔顿问题本来就是NP，没有人会关心其复杂度。
: 每一个大牛的成功背后都有着别人看不到的努力，每一个定理的证明都凝聚着前人不可
: 或缺的基石。世界级猜想，敢碰都算是了不起的人物了。一个20岁的本科生就能解决，
: 你以为这还是欧拉时代么？
|
l*b
发帖数: 11 | 12 吹吧，吹吧
问问 Francis Y.L. Chin 去？
国内流行送礼，有人看看这个郭泽宇的父亲是谁？
想起以前南大那个同学有个北师大的老爹
科大那个同学有个老爹也就发science
这个郭泽宇的老爹是谁？ |
l*****g
发帖数: 2087 | 13 郭坤宇？
【在 l*b 的大作中提到】
: 吹吧，吹吧
: 问问 Francis Y.L. Chin 去？
: 国内流行送礼，有人看看这个郭泽宇的父亲是谁？
: 想起以前南大那个同学有个北师大的老爹
: 科大那个同学有个老爹也就发science
: 这个郭泽宇的老爹是谁？
|
s******a
发帖数: 128 | 14 比较可能的是老师们做的算法，他编的程序。
【在 I*****y 的大作中提到】
: 【 以下文字转载自 ChinaNews 讨论区 】
: 发信人: suite (suite), 信区: ChinaNews
: 标 题: 复旦20岁本科生证明世界级猜想 十余年来未解决
: 发信站: BBS 未名空间站 (Mon Jun 22 02:41:14 2009, 美东)
: 晚报讯 复旦大学昨天传来消息，该校计算机学院大三学生郭泽宇关于最小曼哈顿网络
: 问题的论文被美国ACM学会主办的第25届计算几何国际会议录用，文章同时作为最佳论
: 文之一被邀请投稿到会议特刊(DCG)。
: 这意味着计算几何领域十余年来未决的重要猜想被这位年仅20岁的本科生成功解决。
: 最小曼哈顿网络问题是计算机学院朱洪教授给自己指导的本科生们所开设的题目，
: 在城市规划、网络路由、大规模集成电路设计以及计算生物学等众多领域有着很好的应
|
s*****g
发帖数: 5159 | 15 能把一个well known的open problem证明是NP完全的，对于20岁的本科小伙子来说，可
喜可贺啊。问题有多重要，看看20年来在这个问题上发的论文数量/质量就知道了。
【在 m****n 的大作中提到】
: 靠！这就叫“成功解决十余年来未解决世界级猜想”？！记者脑残啊？
: 我的理解是：如果他的结果是对的，是对现有的算法提高了一些近似度，离“成功解决
: ”远得不是一点半点。
: 当然，考虑到是本科生，还是要大加赞赏，值得嘉奖，前提是这个结果是正确的，呵呵
: 。
|
s*****g
发帖数: 5159 | 16 文章写的明了，语言稍差，值得一读。
不过问题是1999年提出的，参考文献发表的地方我没有能力评价。
【在 s*****g 的大作中提到】
: 能把一个well known的open problem证明是NP完全的，对于20岁的本科小伙子来说，可
: 喜可贺啊。问题有多重要，看看20年来在这个问题上发的论文数量/质量就知道了。
|
m****n
发帖数: 142 | 17 嗯，俺酸葡萄，呵呵。
【在 L*****s 的大作中提到】
: 我看到有人想吃酸葡萄了..
|
a***o
发帖数: 65 | 18 TMD又是复旦的人在那里自吹自擂了，上海的传媒算是毁在复旦的手里了 |
s***n
发帖数: 459 | 19 很少发言，刚好对这个问题有一点了解，说两句．两年前朱洪老师带来这个问题时，提
了一个思路归约到整数规划去找找新算法，我花了几天推到一个自认饶不过去的困难，
也就停止了．两年内朱老师一定将这个问题传给不少人，现在由复旦两个年轻人(２０岁
和２５岁）做出更有价值的hardness证明，非常值得祝贺．
份量．证明直接从SAT归约，造了gadget不止一个而是一套，挺复杂的，这应该是论
文被SＣＧ接受的主要原因．如果证明比较简单可能就发不了这摸高.理论计算机里十几
年没人证明NＰＣ的问题也有一堆，证出NＰＣ的已经几千个了，一流学者对多证一个已
经不敢兴趣．具体到某个题，当初提问题的人说了一句＂目前不知道是否ＮＰＣ＂，然
后就开始近似算法，后面follow的人一定都会花点时间去想"是NPC吗"?我别跟了一个民
科课题呀!把十年follow这个问题的十几篇文章几十个作者圈在一起,他们是得要承认"
你做到了我没做到的".其他人,尤其顶尖的,只会承认"你做到了那几十个人没做到的"而
已.所以"世界级猜想"技术上没错,风格上有点晚报了，这跟数学里歌德巴赫呀蓬加来那
种不一样,那种虽然也是只有几十个人搞, |
l*****g
发帖数: 2087 | 20 现在做science都跟卖鸡蛋差不多了，写个论文恨不得就提个篮子冲到农贸市场去。。
【在 s***n 的大作中提到】
: 很少发言，刚好对这个问题有一点了解，说两句．两年前朱洪老师带来这个问题时，提
: 了一个思路归约到整数规划去找找新算法，我花了几天推到一个自认饶不过去的困难，
: 也就停止了．两年内朱老师一定将这个问题传给不少人，现在由复旦两个年轻人(２０岁
: 和２５岁）做出更有价值的hardness证明，非常值得祝贺．
: 份量．证明直接从SAT归约，造了gadget不止一个而是一套，挺复杂的，这应该是论
: 文被SＣＧ接受的主要原因．如果证明比较简单可能就发不了这摸高.理论计算机里十几
: 年没人证明NＰＣ的问题也有一堆，证出NＰＣ的已经几千个了，一流学者对多证一个已
: 经不敢兴趣．具体到某个题，当初提问题的人说了一句＂目前不知道是否ＮＰＣ＂，然
: 后就开始近似算法，后面follow的人一定都会花点时间去想"是NPC吗"?我别跟了一个民
: 科课题呀!把十年follow这个问题的十几篇文章几十个作者圈在一起,他们是得要承认"
|
|
|
i***q
发帖数: 1095 | 21 SoCG Best Paper， 货真价实的
【在 s*****g 的大作中提到】
: 能把一个well known的open problem证明是NP完全的，对于20岁的本科小伙子来说，可
: 喜可贺啊。问题有多重要，看看20年来在这个问题上发的论文数量/质量就知道了。
|
i***q
发帖数: 1095 | 22 ICM上边演讲过的人，不算没名气吧？
【在 s***n 的大作中提到】
: 很少发言，刚好对这个问题有一点了解，说两句．两年前朱洪老师带来这个问题时，提
: 了一个思路归约到整数规划去找找新算法，我花了几天推到一个自认饶不过去的困难，
: 也就停止了．两年内朱老师一定将这个问题传给不少人，现在由复旦两个年轻人(２０岁
: 和２５岁）做出更有价值的hardness证明，非常值得祝贺．
: 份量．证明直接从SAT归约，造了gadget不止一个而是一套，挺复杂的，这应该是论
: 文被SＣＧ接受的主要原因．如果证明比较简单可能就发不了这摸高.理论计算机里十几
: 年没人证明NＰＣ的问题也有一堆，证出NＰＣ的已经几千个了，一流学者对多证一个已
: 经不敢兴趣．具体到某个题，当初提问题的人说了一句＂目前不知道是否ＮＰＣ＂，然
: 后就开始近似算法，后面follow的人一定都会花点时间去想"是NPC吗"?我别跟了一个民
: 科课题呀!把十年follow这个问题的十几篇文章几十个作者圈在一起,他们是得要承认"
|
l******e
发帖数: 470 | 23 恩，这个比较客观。
很少发言，刚好对这个问题有一点了解，说两句．两年前朱洪老师带来这个问题时，提
了一个思路归约到整数规划，我花了几天推到一个自认饶不过去的困难，也就停止了．
两年内朱老师一定将这个问题传给不少人，现在由复旦两个年轻人(２０岁和２５岁）
做出来，非常值得祝贺．
份量．证明直接归约到SＡＴ，造了gadget不止一个而是一套，挺复杂的，这应该是论
文被SＣＧ接受的主要原因．如果证明比较简单可能就发不了这摸高.理论计算机里十几
年没人证明NＰＣ的问题也有一堆，证出NＰＣ的已经几千个了，一流学者对多证一个已
经不敢兴趣．具体到某个题，当初提问题的人说了一句＂目前不知道是否ＮＰＣ＂，然
后就开始近似算法，后面follow的人一定都会花点时间去想"是NPC吗"?我别跟了一个民
科课题呀!把十年follow这个问题的十几篇文章几十个作者圈在一起,他们是得要承认"
你做到了我没做到的".其他人,尤其顶尖的,只会承认"你做到了那几十个人没做到的"而
已.所以"世界级猜想"技术上没错,风格上有点晚报了，这跟数学里歌德巴赫呀蓬加来那
种不一样,那种虽然也是只有几十个人搞,但是其他数学家会承
【在 s***n 的大作中提到】
: 很少发言，刚好对这个问题有一点了解，说两句．两年前朱洪老师带来这个问题时，提
: 了一个思路归约到整数规划去找找新算法，我花了几天推到一个自认饶不过去的困难，
: 也就停止了．两年内朱老师一定将这个问题传给不少人，现在由复旦两个年轻人(２０岁
: 和２５岁）做出更有价值的hardness证明，非常值得祝贺．
: 份量．证明直接从SAT归约，造了gadget不止一个而是一套，挺复杂的，这应该是论
: 文被SＣＧ接受的主要原因．如果证明比较简单可能就发不了这摸高.理论计算机里十几
: 年没人证明NＰＣ的问题也有一堆，证出NＰＣ的已经几千个了，一流学者对多证一个已
: 经不敢兴趣．具体到某个题，当初提问题的人说了一句＂目前不知道是否ＮＰＣ＂，然
: 后就开始近似算法，后面follow的人一定都会花点时间去想"是NPC吗"?我别跟了一个民
: 科课题呀!把十年follow这个问题的十几篇文章几十个作者圈在一起,他们是得要承认"
|
l******e
发帖数: 470 | 24 就是有一点，socg那能每篇都有几十上百的引用，我觉得大部分都是0-10的引用才对。。
【在 s***n 的大作中提到】
: 很少发言，刚好对这个问题有一点了解，说两句．两年前朱洪老师带来这个问题时，提
: 了一个思路归约到整数规划去找找新算法，我花了几天推到一个自认饶不过去的困难，
: 也就停止了．两年内朱老师一定将这个问题传给不少人，现在由复旦两个年轻人(２０岁
: 和２５岁）做出更有价值的hardness证明，非常值得祝贺．
: 份量．证明直接从SAT归约，造了gadget不止一个而是一套，挺复杂的，这应该是论
: 文被SＣＧ接受的主要原因．如果证明比较简单可能就发不了这摸高.理论计算机里十几
: 年没人证明NＰＣ的问题也有一堆，证出NＰＣ的已经几千个了，一流学者对多证一个已
: 经不敢兴趣．具体到某个题，当初提问题的人说了一句＂目前不知道是否ＮＰＣ＂，然
: 后就开始近似算法，后面follow的人一定都会花点时间去想"是NPC吗"?我别跟了一个民
: 科课题呀!把十年follow这个问题的十几篇文章几十个作者圈在一起,他们是得要承认"
|
s***n
发帖数: 459 | 25 Over the years...当然每篇不妥,应该说many
。。
【在 l******e 的大作中提到】
: 就是有一点，socg那能每篇都有几十上百的引用，我觉得大部分都是0-10的引用才对。。
|
e***e
发帖数: 53 | 26 这是个perfect-for-brilliant-undergrads的题目：
1. 技巧相对较elementary（当然整个CS理论甚至组合数学都不算很advanced）
2. 够难但是难得“不划算”。
希望这么说不会被误解，并不是说这个问题不重要。而是reduction的结果单凭它的难
度已经不再能够刺激人们的神经了，除非这个reduction能够像PCP那样成为一个有用的
工具，或者像equalibrium是PPAD-hard这样有"conceptual contribution"。
其实理论CS经常有一些所谓“过时”的猜想被本科生证明，许多都是自动机方面的，就
被正在修计算理论的学生给作了。虽然理论的“主流”趣味已经转移了，但这样的结果
至少good-to-know，而且有些具有很漂亮的结构。我个人很喜欢这样的结果，且认为计
算机理论领域对这些结果的相对忽视是由CS功利主义的劣根造成的。
复旦SCG这道题显然要不过时多了，因为至少这个题目的upper bound方向一直在进行中
，lower bound显然是很有意义的。
国内的本科生多参与这样的研究是非常好的，而且这种题目的选 |
w**********s
发帖数: 291 | 27 看了几个帖子，还说得比较客观。个人感觉，这首先是很值得肯定的一件事情。
其次，是媒体（或许还有论文的合作者），有点夸张了。“世界级”是个很模糊的字眼
，只是能有效刺激民众的眼球。
国内的CS，基础研究远比不上应用研究热，都是因为把“科研产业化”看得太重。这样
的工作得多一点才好。学校的人应该避免浮躁的宣传。国内CS不管什么方面，重量级的
成果几乎没有。离这个目标还很远！ |
v********e
发帖数: 1058 | 28 yzy是谁？
【在 e***e 的大作中提到】
: 这是个perfect-for-brilliant-undergrads的题目：
: 1. 技巧相对较elementary（当然整个CS理论甚至组合数学都不算很advanced）
: 2. 够难但是难得“不划算”。
: 希望这么说不会被误解，并不是说这个问题不重要。而是reduction的结果单凭它的难
: 度已经不再能够刺激人们的神经了，除非这个reduction能够像PCP那样成为一个有用的
: 工具，或者像equalibrium是PPAD-hard这样有"conceptual contribution"。
: 其实理论CS经常有一些所谓“过时”的猜想被本科生证明，许多都是自动机方面的，就
: 被正在修计算理论的学生给作了。虽然理论的“主流”趣味已经转移了，但这样的结果
: 至少good-to-know，而且有些具有很漂亮的结构。我个人很喜欢这样的结果，且认为计
: 算机理论领域对这些结果的相对忽视是由CS功利主义的劣根造成的。
|
e***e
发帖数: 53 | 29 某个当年的高中竞赛明星，保送复旦，后从复旦高调退学。等再次从网上看到这个名字
，俨然民科矣。
【在 v********e 的大作中提到】
: yzy是谁？
|
l******e
发帖数: 470 | 30 我觉得组合学由于近几十年的发展已经很advanced了
【在 e***e 的大作中提到】
: 这是个perfect-for-brilliant-undergrads的题目：
: 1. 技巧相对较elementary（当然整个CS理论甚至组合数学都不算很advanced）
: 2. 够难但是难得“不划算”。
: 希望这么说不会被误解，并不是说这个问题不重要。而是reduction的结果单凭它的难
: 度已经不再能够刺激人们的神经了，除非这个reduction能够像PCP那样成为一个有用的
: 工具，或者像equalibrium是PPAD-hard这样有"conceptual contribution"。
: 其实理论CS经常有一些所谓“过时”的猜想被本科生证明，许多都是自动机方面的，就
: 被正在修计算理论的学生给作了。虽然理论的“主流”趣味已经转移了，但这样的结果
: 至少good-to-know，而且有些具有很漂亮的结构。我个人很喜欢这样的结果，且认为计
: 算机理论领域对这些结果的相对忽视是由CS功利主义的劣根造成的。
|
|
|
g*****s
发帖数: 1288 | 31 佩服。屁都没明白就敢放
【在 J*****n 的大作中提到】
:
: 酸个屁，哈密尔顿问题本来就是NP，没有人会关心其复杂度。
: 每一个大牛的成功背后都有着别人看不到的努力，每一个定理的证明都凝聚着前人不可
: 或缺的基石。世界级猜想，敢碰都算是了不起的人物了。一个20岁的本科生就能解决，
: 你以为这还是欧拉时代么？
|
b***u
发帖数: 634 | 32 我倒是觉得20岁左右是头脑最活跃的时候，尤其我们中国的孩子们，其实都很聪明的，
只是国内高校太缺少让年轻人接触世界科学前沿的机会了，这个最主要原因是大学里的
导师本身水平就有限
所以现在国内高校在广泛聘请国外有研究经验的人回国也是个很好的开端 |
l*****g
发帖数: 49 | 33 很客观，不过 SoCG 好像没有 best paper award.
就算有这篇 Paper 也不太可能得. 即使在同类型 Paper 里，这次 SoCG 另一篇
Maximum Degree Four Euclidean Minimum Spanning Tree is NP-hard
那个问题更被关注，Open 的时间也更长。
Anyway 就像你说的，证明某个问题 NP hard 属于３０年前的热点，已经不再让人兴奋
了.
这是个perfect-for-brilliant-undergrads的题目：
1. 技巧相对较elementary（当然整个CS理论甚至组合数学都不算很advanced）
2. 够难但是难得“不划算”。
希望这么说不会被误解，并不是说这个问题不重要。而是reduction的结果单凭它的难
度已经不再能够刺激人们的神经了，除非这个reduction能够像PCP那样成为一个有用的
工具，或者像equalibrium是PPAD-hard这样有"conceptual contribution"。
其实理论CS经常有一些所谓“过时”的猜想被本科生证明，许多都是自动机
【在 e***e 的大作中提到】
: 这是个perfect-for-brilliant-undergrads的题目：
: 1. 技巧相对较elementary（当然整个CS理论甚至组合数学都不算很advanced）
: 2. 够难但是难得“不划算”。
: 希望这么说不会被误解，并不是说这个问题不重要。而是reduction的结果单凭它的难
: 度已经不再能够刺激人们的神经了，除非这个reduction能够像PCP那样成为一个有用的
: 工具，或者像equalibrium是PPAD-hard这样有"conceptual contribution"。
: 其实理论CS经常有一些所谓“过时”的猜想被本科生证明，许多都是自动机方面的，就
: 被正在修计算理论的学生给作了。虽然理论的“主流”趣味已经转移了，但这样的结果
: 至少good-to-know，而且有些具有很漂亮的结构。我个人很喜欢这样的结果，且认为计
: 算机理论领域对这些结果的相对忽视是由CS功利主义的劣根造成的。
|
e***e
发帖数: 53 | 34 You are right. I must be wrong about it.
【在 l*****g 的大作中提到】
: 很客观，不过 SoCG 好像没有 best paper award.
: 就算有这篇 Paper 也不太可能得. 即使在同类型 Paper 里，这次 SoCG 另一篇
: Maximum Degree Four Euclidean Minimum Spanning Tree is NP-hard
: 那个问题更被关注，Open 的时间也更长。
: Anyway 就像你说的，证明某个问题 NP hard 属于３０年前的热点，已经不再让人兴奋
: 了.
:
: 这是个perfect-for-brilliant-undergrads的题目：
: 1. 技巧相对较elementary（当然整个CS理论甚至组合数学都不算很advanced）
: 2. 够难但是难得“不划算”。
|
e***e
发帖数: 53 | 35 combinatorics today indeed uses many advanced techniques, like algebraic or
analysis techniques. But it is still possible for a non-expert to understand
a seminar of the subject or pick up a combinatorial problem, which is never
gonna happen for those advanced-in-the-root areas like differential
geometry or topology. In this sense, combinatorics still remains some user-
friendly interfaces:)
【在 l******e 的大作中提到】
: 我觉得组合学由于近几十年的发展已经很advanced了
|
g****t
发帖数: 31659 | 36 x'=f(x),x是2维的，f是多项式;
则此方程最多存在有限个周期解。
这是个大一学生都可以看懂的问题，苏联人对这
个问题的解决使用的方法一点也不抽象和先进。我们机械系的都可以理解。
按你的想法，这就是个非advanced问题？这是希尔伯特某问题，
两组搞定的人都做过大会报告的。
198x年，KAM定理被人搞了个 排列组合+树图 的构造性证明，
这是非advance问题吗？
combinatorics today indeed uses many advanced techniques, like algebraic or
analysis techniques. But it is still possible for a non-expert to understand
a seminar of the subject or pick up a combinatorial problem, which is never
gonna happen for those advanced-in-the-root areas like differential
geometry or
【在 e***e 的大作中提到】
: combinatorics today indeed uses many advanced techniques, like algebraic or
: analysis techniques. But it is still possible for a non-expert to understand
: a seminar of the subject or pick up a combinatorial problem, which is never
: gonna happen for those advanced-in-the-root areas like differential
: geometry or topology. In this sense, combinatorics still remains some user-
: friendly interfaces:)
|
r******o
发帖数: 122 | 37
请教书目，或link?
【在 g****t 的大作中提到】
: x'=f(x),x是2维的，f是多项式;
: 则此方程最多存在有限个周期解。
: 这是个大一学生都可以看懂的问题，苏联人对这
: 个问题的解决使用的方法一点也不抽象和先进。我们机械系的都可以理解。
: 按你的想法，这就是个非advanced问题？这是希尔伯特某问题，
: 两组搞定的人都做过大会报告的。
: 198x年，KAM定理被人搞了个 排列组合+树图 的构造性证明，
: 这是非advance问题吗？
:
: combinatorics today indeed uses many advanced techniques, like algebraic or
|
g****t
发帖数: 31659 | 38 198x年代，L.H.Eliason写了一个小分母问题圈子内很有名的东西，
一直到1996年才发表在
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.9483
这是小分母问题方法上的重大进展。后来很多人
都在这个方向灌水，例如:
例如:
KAM theorem revisited
G. Gentilea and V. Mastropietrob
a Dipartimento di Fisica, Università di Roma “La Sapienza”, 00185, Roma,
Italy
b Dipartimento di Matematica, Università di Roma II “Tor Vergata”, 00133,
Roma, Italy
Received 30 December 1994;
revised 30 July 1995;
accepted 15 August 1995;
Communicated by V.I. Arnol'd
A combinatorial proof o
【在 r******o 的大作中提到】
:
: 请教书目，或link?
|
l******e
发帖数: 470 | 39 其实就举组合的例子就够说明问题了
早了点说Tutte那一套，非常的代数
近点说Lovasz,非常的拓扑
要说deep，最好的例子graph minor theorem, 证明是一个系列20多篇journal paper，
快上千页了，这个够deep了吧。
我是看不出哪点不advance了
不过说牛人不一定不这么认为
我记得Dingzhu Du给我讲过个故事，说他在中科院数学所的时候见华罗庚，
Du那时可能还年轻， 华问Du 作什么，Du说做优化（实际是组合优化）
华罗庚说“哦，优化呀，优化简单”，呵呵
mitbbs上也是藏龙卧虎。
,
【在 g****t 的大作中提到】
: 198x年代，L.H.Eliason写了一个小分母问题圈子内很有名的东西，
: 一直到1996年才发表在
: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.9483
: 这是小分母问题方法上的重大进展。后来很多人
: 都在这个方向灌水，例如:
: 例如:
: KAM theorem revisited
: G. Gentilea and V. Mastropietrob
: a Dipartimento di Fisica, Università di Roma “La Sapienza”, 00185, Roma,
: Italy
|
g****t
发帖数: 31659 | 40 牛人出了自己熟悉的那一块，也就跟文盲差不了太多。
能者无所不能，那是中国的胡扯逻辑。
华不是专职搞优化的，说错话不稀罕。
其实就举组合的例子就够说明问题了
早了点说Tutte那一套，非常的代数
近点说Lovasz,非常的拓扑
要说deep，最好的例子graph minor theorem, 证明是一个系列20多篇journal paper，
快上千页了，这个够deep了吧。
我是看不出哪点不advance了
不过说牛人不一定不这么认为
我记得Dingzhu Du给我讲过个故事，说他在中科院数学所的时候见华罗庚，
Du那时可能还年轻， 华问Du 作什么，Du说做优化（实际是组合优化）
华罗庚说“哦，优化呀，优化简单”，呵呵
mitbbs上也是藏龙卧虎。
,
【在 l******e 的大作中提到】
: 其实就举组合的例子就够说明问题了
: 早了点说Tutte那一套，非常的代数
: 近点说Lovasz,非常的拓扑
: 要说deep，最好的例子graph minor theorem, 证明是一个系列20多篇journal paper，
: 快上千页了，这个够deep了吧。
: 我是看不出哪点不advance了
: 不过说牛人不一定不这么认为
: 我记得Dingzhu Du给我讲过个故事，说他在中科院数学所的时候见华罗庚，
: Du那时可能还年轻， 华问Du 作什么，Du说做优化（实际是组合优化）
: 华罗庚说“哦，优化呀，优化简单”，呵呵
|
|
|
e***e
发帖数: 53 | 41 技巧advanced还是elementary，这和篇幅长短恐怕关系不大。PCP的原始证明也很长，
但要说用到的数学，可能一个高年级的计算机本科生就看的懂了。
你举的lovasz和graph minor theory的例子，follow这些结果的人，很多是计算机科学
的人，许多人也自认没什么深厚数学背景。至少这些paper普通人拿上手都能看看。但
如果换成微分几何的，可能连定理说什么都看不懂，要回头backtrack一些基础概念。
这就是所谓elementary/advanced的区别。
如果不是硬要抬杠的话，我想这里的大部分人，至少对什么technique是elementary/
advanced以及什么领域是elementary/advanced有个general的常识。但这不是绝对的，
同一个问题可能同时有elementary和advanced proof，素数定理就是这样。也不必钻牛
角尖的具例说明所谓elementery 的领域有多么advance的结果，你肯定找得到。如果这
个说法是严格的话，早就有metamathematics的人把它定义出来了。
【在 l******e 的大作中提到】
: 其实就举组合的例子就够说明问题了
: 早了点说Tutte那一套，非常的代数
: 近点说Lovasz,非常的拓扑
: 要说deep，最好的例子graph minor theorem, 证明是一个系列20多篇journal paper，
: 快上千页了，这个够deep了吧。
: 我是看不出哪点不advance了
: 不过说牛人不一定不这么认为
: 我记得Dingzhu Du给我讲过个故事，说他在中科院数学所的时候见华罗庚，
: Du那时可能还年轻， 华问Du 作什么，Du说做优化（实际是组合优化）
: 华罗庚说“哦，优化呀，优化简单”，呵呵
|
l******e
发帖数: 470 | 42 lovasz 是写过几个能让你看懂的proof，也不至于你一句话就把整个组合变成
elementary了
graph minor普通人拿上手能看看？cs里follow这个work的有几个真看过这个（当然有
几个。。），大部分都是用里面的概念和结论。我同意PCP可能被一个高年机本科生看
懂，你的微分几何照样可能被高年级数学系本科生看动，只不过你看不懂罢了，你不能
因为你懂什么什么就elementary。
不能否认我在抬杠，但我说的有道理，呵呵
【在 e***e 的大作中提到】
: 技巧advanced还是elementary，这和篇幅长短恐怕关系不大。PCP的原始证明也很长，
: 但要说用到的数学，可能一个高年级的计算机本科生就看的懂了。
: 你举的lovasz和graph minor theory的例子，follow这些结果的人，很多是计算机科学
: 的人，许多人也自认没什么深厚数学背景。至少这些paper普通人拿上手都能看看。但
: 如果换成微分几何的，可能连定理说什么都看不懂，要回头backtrack一些基础概念。
: 这就是所谓elementary/advanced的区别。
: 如果不是硬要抬杠的话，我想这里的大部分人，至少对什么technique是elementary/
: advanced以及什么领域是elementary/advanced有个general的常识。但这不是绝对的，
: 同一个问题可能同时有elementary和advanced proof，素数定理就是这样。也不必钻牛
: 角尖的具例说明所谓elementery 的领域有多么advance的结果，你肯定找得到。如果这
|
e***e
发帖数: 53 | 43 我不懂你抬杠个什么劲，我本人就是CS理论和组合数学方向的，至少这个方向的大多数
人包括我都觉得being elementary是这个方向的特色。如果一个问题同时有初等证明和
非初等证明的话，通常初等证明都更有价值，除非那个非初等证明还能说明一些其他的
东西。否则也不会有"the book proof"这种说法。
我不明白你在跟我争什么。
【在 l******e 的大作中提到】
: lovasz 是写过几个能让你看懂的proof，也不至于你一句话就把整个组合变成
: elementary了
: graph minor普通人拿上手能看看？cs里follow这个work的有几个真看过这个（当然有
: 几个。。），大部分都是用里面的概念和结论。我同意PCP可能被一个高年机本科生看
: 懂，你的微分几何照样可能被高年级数学系本科生看动，只不过你看不懂罢了，你不能
: 因为你懂什么什么就elementary。
: 不能否认我在抬杠，但我说的有道理，呵呵
|
e***e
发帖数: 53 | 44 关于graph minor theorem，它的proof的一个核心是一个算法。从这个角度来说，不是
算法的人用graph minor theory的概念和结论，而是反过来。
当然在其他问题上，算法也引用graph minor theory的结论。
【在 l******e 的大作中提到】
: lovasz 是写过几个能让你看懂的proof，也不至于你一句话就把整个组合变成
: elementary了
: graph minor普通人拿上手能看看？cs里follow这个work的有几个真看过这个（当然有
: 几个。。），大部分都是用里面的概念和结论。我同意PCP可能被一个高年机本科生看
: 懂，你的微分几何照样可能被高年级数学系本科生看动，只不过你看不懂罢了，你不能
: 因为你懂什么什么就elementary。
: 不能否认我在抬杠，但我说的有道理，呵呵
|
l******e
发帖数: 470 | 45 我知道你是搞cs的，但我很怀疑你搞组合，that is all.
【在 e***e 的大作中提到】
: 我不懂你抬杠个什么劲，我本人就是CS理论和组合数学方向的，至少这个方向的大多数
: 人包括我都觉得being elementary是这个方向的特色。如果一个问题同时有初等证明和
: 非初等证明的话，通常初等证明都更有价值，除非那个非初等证明还能说明一些其他的
: 东西。否则也不会有"the book proof"这种说法。
: 我不明白你在跟我争什么。
|
l******e
发帖数: 470 | 46 拜托graph minor thm是nonconstructive的。另外你不能说人家搞出来个算法就变成搞
算法的人，大家心理都清楚搞算法的community是哪个。而在这个问题上谁follow谁是
显然的。
【在 e***e 的大作中提到】
: 关于graph minor theorem，它的proof的一个核心是一个算法。从这个角度来说，不是
: 算法的人用graph minor theory的概念和结论，而是反过来。
: 当然在其他问题上，算法也引用graph minor theory的结论。
|
e***e
发帖数: 53 | 47 graph minor theory并非完全是nonconstrucive的。否则也不会motivate出property
testing这道题目了
这个请参见maria chudnovsky近几年在算法方向上的工作和合作。我记得Widgerson在
某年的ICM上也给了一个talk提到了（efficient）算法和graph minor theory的联系，
他用这个例子来用理论计算机科学来impress数学家。
【在 l******e 的大作中提到】
: 拜托graph minor thm是nonconstructive的。另外你不能说人家搞出来个算法就变成搞
: 算法的人，大家心理都清楚搞算法的community是哪个。而在这个问题上谁follow谁是
: 显然的。
|
e***e
发帖数: 53 | 48 我个人搞什么完全不重要。但有点数学sense的人都起码对初等／非初等有点共通的认
识，而且这种认识应该是nuetrual的，而不是偏要互相鄙视，在这个基础上才能正常的
交流。你如果应要歪着脖子证明组合数学比代数拓扑“非初等”，我也没办法。
现实中见到的combinatorist，包括你提到的那位，还没有那个对这种无谓的事而气急
败坏的。大部分是把自己的“初等”作为常态了。Zeilberger曾经抱怨过tian的ICM
talk很糟，因为让人听不懂。这也显出了两个方向不同的伦理，数学的很多方向，根本
就没奢望过要不做的人听懂。
【在 l******e 的大作中提到】
: 我知道你是搞cs的，但我很怀疑你搞组合，that is all.
|
s***n
发帖数: 459 | 49 两位学术讨论开了...见到同行很高兴,大家交个朋友吧. |
e***e
发帖数: 53 | 50 讨论的根本不是学术，而是在抬杠和抠字眼，就怕别人以为搞数学的不够穷酸。
【在 s***n 的大作中提到】
: 两位学术讨论开了...见到同行很高兴,大家交个朋友吧.
|
|
|
l******e
发帖数: 470 | 51 我的point就一个，就是组合不初等，不和哪个领域比
你说一个proof是初等，是夸这个proof，你说一个领域初等，我就看不出来是夸了，
我还不是做组合的都看不下去了，更何况是真正在做这个领域的，你提到一群一群名字
，你给他们发email，告诉他们你门做的太初等，他们估计都气死了，呵呵
【在 e***e 的大作中提到】
: 我个人搞什么完全不重要。但有点数学sense的人都起码对初等／非初等有点共通的认
: 识，而且这种认识应该是nuetrual的，而不是偏要互相鄙视，在这个基础上才能正常的
: 交流。你如果应要歪着脖子证明组合数学比代数拓扑“非初等”，我也没办法。
: 现实中见到的combinatorist，包括你提到的那位，还没有那个对这种无谓的事而气急
: 败坏的。大部分是把自己的“初等”作为常态了。Zeilberger曾经抱怨过tian的ICM
: talk很糟，因为让人听不懂。这也显出了两个方向不同的伦理，数学的很多方向，根本
: 就没奢望过要不做的人听懂。
|
l******e
发帖数: 470 | 52 谢谢支持我的point。
【在 e***e 的大作中提到】
: graph minor theory并非完全是nonconstrucive的。否则也不会motivate出property
: testing这道题目了
: 这个请参见maria chudnovsky近几年在算法方向上的工作和合作。我记得Widgerson在
: 某年的ICM上也给了一个talk提到了（efficient）算法和graph minor theory的联系，
: 他用这个例子来用理论计算机科学来impress数学家。
|
l******e
发帖数: 470 | 53 我不搞数学，谢谢
我就是觉得兄弟你指点江山特有豪情，特来置疑一下，没别的意思，别伤了和气，呵呵。
【在 e***e 的大作中提到】
: 讨论的根本不是学术，而是在抬杠和抠字眼，就怕别人以为搞数学的不够穷酸。
|
e***e
发帖数: 53 | 54 那我们可能无法做有效的交流了，elementary与否本身就是个相对的概念。没有人定义
什么是elementary，只是大家心里有这么个大约的谱系。
我承认如果说整个领域都初等是不合适的。初等是用来形容工具的，只是不同方向的问
题适合不同工具，有一个大概的偏好。我不觉的评价工作是初等的会气到谁，也许你凭
想当然的这么认为，但至少现实中我见到的combinatorist还没有这样的。
【在 l******e 的大作中提到】
: 我的point就一个，就是组合不初等，不和哪个领域比
: 你说一个proof是初等，是夸这个proof，你说一个领域初等，我就看不出来是夸了，
: 我还不是做组合的都看不下去了，更何况是真正在做这个领域的，你提到一群一群名字
: ，你给他们发email，告诉他们你门做的太初等，他们估计都气死了，呵呵
|
e***e
发帖数: 53 | 55 劝你还是至少了解一下graph minor theory以及finite-basis theorem和算法的等价性
，再来决定什么有没有支持你的point不迟。
【在 l******e 的大作中提到】
: 谢谢支持我的point。
|
e***e
发帖数: 53 | 56 我没有什么豪情，只是尽量nuetral客观的说话罢了。相比诸位的插科打诨、阴阳怪气
，的确有些不合时宜，但确实没有什么豪情。
呵。
【在 l******e 的大作中提到】
: 我不搞数学，谢谢
: 我就是觉得兄弟你指点江山特有豪情，特来置疑一下，没别的意思，别伤了和气，呵呵。
|
v********e
发帖数: 1058 | 57 我打酱油的，不过我觉得lapordge没气急败坏。现在在bbs上看见这种双方平心静气的
讨论还挺难得的。
【在 e***e 的大作中提到】
: 我个人搞什么完全不重要。但有点数学sense的人都起码对初等／非初等有点共通的认
: 识，而且这种认识应该是nuetrual的，而不是偏要互相鄙视，在这个基础上才能正常的
: 交流。你如果应要歪着脖子证明组合数学比代数拓扑“非初等”，我也没办法。
: 现实中见到的combinatorist，包括你提到的那位，还没有那个对这种无谓的事而气急
: 败坏的。大部分是把自己的“初等”作为常态了。Zeilberger曾经抱怨过tian的ICM
: talk很糟，因为让人听不懂。这也显出了两个方向不同的伦理，数学的很多方向，根本
: 就没奢望过要不做的人听懂。
|
s***n
发帖数: 459 | 58 哈哈lapordge你这个抱不平打得太多虑了,我们做组合的命贱着呢,自嘲是我们的标签,
从大牛牛到小虫虫,装逼的不选这行.你要听故事那多啦.etone说的是我们内行话,那群
人自己也说,怎么可能生气.就象凌蜂唱的"小丑",我们的坚强和泪水是在幕后那一个个
不眠的夜里.看看堵丁柱,比比陆嘉羲,再不您就Erdos,谁还敢装逼!?
【在 l******e 的大作中提到】
: 我不搞数学，谢谢
: 我就是觉得兄弟你指点江山特有豪情，特来置疑一下，没别的意思，别伤了和气，呵呵。
|
a*******h
发帖数: 123 | 59 胡乱评论一下.
很少看到有 hardness proof 是从整数规划归约的, 感觉约束条件里面整数乘以变量这
种项不容易 model.
3SAT还是结构简单多了,而且有无数种 specialization 也还是 hard. 其实他们文章里
面用的 gadgets 除了有一个所谓的 adapter 之外, 其他都是很常见的 gadgets. 我猜
他们论文被接受的原因应该是因为他们解决了计算几何里面几十年的 Open Problem,,
否则就凭一个 hardness proof 肯定中不了SoCG.
【在 s***n 的大作中提到】
: 很少发言，刚好对这个问题有一点了解，说两句．两年前朱洪老师带来这个问题时，提
: 了一个思路归约到整数规划去找找新算法，我花了几天推到一个自认饶不过去的困难，
: 也就停止了．两年内朱老师一定将这个问题传给不少人，现在由复旦两个年轻人(２０岁
: 和２５岁）做出更有价值的hardness证明，非常值得祝贺．
: 份量．证明直接从SAT归约，造了gadget不止一个而是一套，挺复杂的，这应该是论
: 文被SＣＧ接受的主要原因．如果证明比较简单可能就发不了这摸高.理论计算机里十几
: 年没人证明NＰＣ的问题也有一堆，证出NＰＣ的已经几千个了，一流学者对多证一个已
: 经不敢兴趣．具体到某个题，当初提问题的人说了一句＂目前不知道是否ＮＰＣ＂，然
: 后就开始近似算法，后面follow的人一定都会花点时间去想"是NPC吗"?我别跟了一个民
: 科课题呀!把十年follow这个问题的十几篇文章几十个作者圈在一起,他们是得要承认"
|
f*********g
发帖数: 632 | 60 哪能这样说话不婉转涅？怪不得抬杠。
【在 e***e 的大作中提到】
: 讨论的根本不是学术，而是在抬杠和抠字眼，就怕别人以为搞数学的不够穷酸。
|
|
|
l******e
发帖数: 470 | 61 原来这样啊，我就是没有从etone兄的第一篇洋洋洒洒的雄文中体会到他原来是自嘲呢
啊。，早知道我费这劲干吗，呵呵。
【在 s***n 的大作中提到】
: 哈哈lapordge你这个抱不平打得太多虑了,我们做组合的命贱着呢,自嘲是我们的标签,
: 从大牛牛到小虫虫,装逼的不选这行.你要听故事那多啦.etone说的是我们内行话,那群
: 人自己也说,怎么可能生气.就象凌蜂唱的"小丑",我们的坚强和泪水是在幕后那一个个
: 不眠的夜里.看看堵丁柱,比比陆嘉羲,再不您就Erdos,谁还敢装逼!?
|
a*******h
发帖数: 123 | 62 google了一下, 另外一个作者叫孙贺, 是指导他的博士生, 他们一起之前就发了两篇做
Minimum Manhattan Network 的文章了 http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/g/Guo:Zeyu.html
【在 s***n 的大作中提到】
: 很少发言，刚好对这个问题有一点了解，说两句．两年前朱洪老师带来这个问题时，提
: 了一个思路归约到整数规划去找找新算法，我花了几天推到一个自认饶不过去的困难，
: 也就停止了．两年内朱老师一定将这个问题传给不少人，现在由复旦两个年轻人(２０岁
: 和２５岁）做出更有价值的hardness证明，非常值得祝贺．
: 份量．证明直接从SAT归约，造了gadget不止一个而是一套，挺复杂的，这应该是论
: 文被SＣＧ接受的主要原因．如果证明比较简单可能就发不了这摸高.理论计算机里十几
: 年没人证明NＰＣ的问题也有一堆，证出NＰＣ的已经几千个了，一流学者对多证一个已
: 经不敢兴趣．具体到某个题，当初提问题的人说了一句＂目前不知道是否ＮＰＣ＂，然
: 后就开始近似算法，后面follow的人一定都会花点时间去想"是NPC吗"?我别跟了一个民
: 科课题呀!把十年follow这个问题的十几篇文章几十个作者圈在一起,他们是得要承认"
|
e***e
发帖数: 53 | 63 这个说的很有心得。我看到说整数规划的时候也觉得奇怪来着，不过我想可能未必是指
0-1 IP。但如果是其他special case的话岂不是还要证那个是hard的。
,
【在 a*******h 的大作中提到】
: 胡乱评论一下.
: 很少看到有 hardness proof 是从整数规划归约的, 感觉约束条件里面整数乘以变量这
: 种项不容易 model.
: 3SAT还是结构简单多了,而且有无数种 specialization 也还是 hard. 其实他们文章里
: 面用的 gadgets 除了有一个所谓的 adapter 之外, 其他都是很常见的 gadgets. 我猜
: 他们论文被接受的原因应该是因为他们解决了计算几何里面几十年的 Open Problem,,
: 否则就凭一个 hardness proof 肯定中不了SoCG.
|
s***n
发帖数: 459 | 64 在图上做一点小手法,把约束写成线性不等式,或做另外的小手法,把目标写成线性和,都
不难.但是我这两个小手法完全不兼容,想了几天觉的没有任何可能把两者同时线性,决
定放弃了.这些当时朱教授还记录说回去给学生看,我自己反而没记,印象很模糊,反正没
价值.
但是有一点我想起来了,当是我们是想归约到IP,然后按解IP弄个新的算法,根本不是从
IP归约过来证NPC.所以这一点我最初的贴子说错了,要更正.
MIT灌水也要有严肃态度啊.
【在 e***e 的大作中提到】
: 这个说的很有心得。我看到说整数规划的时候也觉得奇怪来着，不过我想可能未必是指
: 0-1 IP。但如果是其他special case的话岂不是还要证那个是hard的。
:
: ,
|
s***n
发帖数: 459 | 65 我也不记得SoCG有,但是每年会挑五六篇好稿子邀到某个期刊出个专辑,我也被邀
过(不好意思SoCG只灌过一次,但是被邀了,我的业务水平真的很低).小报说最佳论文之
一,说不定就是这个被邀的事,和那个"世界级"一样,这里也应该说"优秀论文之一"或"高
质量论文之一"比较好.这是假设没得 best paper award 的情况.
【在 l*****g 的大作中提到】
: 很客观，不过 SoCG 好像没有 best paper award.
: 就算有这篇 Paper 也不太可能得. 即使在同类型 Paper 里，这次 SoCG 另一篇
: Maximum Degree Four Euclidean Minimum Spanning Tree is NP-hard
: 那个问题更被关注，Open 的时间也更长。
: Anyway 就像你说的，证明某个问题 NP hard 属于３０年前的热点，已经不再让人兴奋
: 了.
:
: 这是个perfect-for-brilliant-undergrads的题目：
: 1. 技巧相对较elementary（当然整个CS理论甚至组合数学都不算很advanced）
: 2. 够难但是难得“不划算”。
|
a*******h
发帖数: 123 | 66 目标和无所谓吧, 感觉就算问 IP 是不是有可行解也是 hard?
写成 IP 之后可以再搞搞 LP Rounding :)
【在 s***n 的大作中提到】
: 在图上做一点小手法,把约束写成线性不等式,或做另外的小手法,把目标写成线性和,都
: 不难.但是我这两个小手法完全不兼容,想了几天觉的没有任何可能把两者同时线性,决
: 定放弃了.这些当时朱教授还记录说回去给学生看,我自己反而没记,印象很模糊,反正没
: 价值.
: 但是有一点我想起来了,当是我们是想归约到IP,然后按解IP弄个新的算法,根本不是从
: IP归约过来证NPC.所以这一点我最初的贴子说错了,要更正.
: MIT灌水也要有严肃态度啊.
|
a*******h
发帖数: 123 | 67 很强悍了, 我只被据过一次 :(
好像会被邀请到 DCG 或者 CGTA 发表.
【在 s***n 的大作中提到】
: 我也不记得SoCG有,但是每年会挑五六篇好稿子邀到某个期刊出个专辑,我也被邀
: 过(不好意思SoCG只灌过一次,但是被邀了,我的业务水平真的很低).小报说最佳论文之
: 一,说不定就是这个被邀的事,和那个"世界级"一样,这里也应该说"优秀论文之一"或"高
: 质量论文之一"比较好.这是假设没得 best paper award 的情况.
|
s***n
发帖数: 459 | 68 haha,that was the plan.
【在 a*******h 的大作中提到】
: 很强悍了, 我只被据过一次 :(
: 好像会被邀请到 DCG 或者 CGTA 发表.
|
m*****n
发帖数: 3575 | 69 这些回帖充分证明了数学留给人的机会有多少，少到人都变态了。
凡是贬低民科，小科的人都是拿历史上其它什么来比，没哪个拿自己做出来的东西来比
，不过是可怜的小市民罢了。 |
v********e
发帖数: 1058 | 70 版上这么多做计算几何的呵。。
【在 a*******h 的大作中提到】
: 很强悍了, 我只被据过一次 :(
: 好像会被邀请到 DCG 或者 CGTA 发表.
|
|
|
w******p
发帖数: 194 | 71 这个我听过作者的talk，idea就是这个本科生的，很厉害。
问题显然也算比较重要，世界级算不上，但确实是做了20年了没人做出来。
总之本科生能做出socg来已经很猛了 |
g****t
发帖数: 31659 | 72 etone说了:
这没啥advanced的，不过是适合本科生的习题而已。
另外他想讲的重点是:
不排除这位本科生将来沦为民科的可能。
hoho
这个我听过作者的talk，idea就是这个本科生的，很厉害。
问题显然也算比较重要，世界级算不上，但确实是做了20年了没人做出来。
总之本科生能做出socg来已经很猛了
【在 w******p 的大作中提到】
: 这个我听过作者的talk，idea就是这个本科生的，很厉害。
: 问题显然也算比较重要，世界级算不上，但确实是做了20年了没人做出来。
: 总之本科生能做出socg来已经很猛了
|
o****e
发帖数: 92 | 73 They proved NPC of the Minimal *Manhattan* Network Problem
by polynomially reducing the well-know 3SAT problem to MMN
【在 J*****n 的大作中提到】
:
: 酸个屁，哈密尔顿问题本来就是NP，没有人会关心其复杂度。
: 每一个大牛的成功背后都有着别人看不到的努力，每一个定理的证明都凝聚着前人不可
: 或缺的基石。世界级猜想，敢碰都算是了不起的人物了。一个20岁的本科生就能解决，
: 你以为这还是欧拉时代么？
|
l***i
发帖数: 632 | 74 组合数学有的也要用到很advanced东西的...
只不过reduction这些东西不需要什么advanced知识
【在 e***e 的大作中提到】
: 这是个perfect-for-brilliant-undergrads的题目：
: 1. 技巧相对较elementary（当然整个CS理论甚至组合数学都不算很advanced）
: 2. 够难但是难得“不划算”。
: 希望这么说不会被误解，并不是说这个问题不重要。而是reduction的结果单凭它的难
: 度已经不再能够刺激人们的神经了，除非这个reduction能够像PCP那样成为一个有用的
: 工具，或者像equalibrium是PPAD-hard这样有"conceptual contribution"。
: 其实理论CS经常有一些所谓“过时”的猜想被本科生证明，许多都是自动机方面的，就
: 被正在修计算理论的学生给作了。虽然理论的“主流”趣味已经转移了，但这样的结果
: 至少good-to-know，而且有些具有很漂亮的结构。我个人很喜欢这样的结果，且认为计
: 算机理论领域对这些结果的相对忽视是由CS功利主义的劣根造成的。
|
l***i
发帖数: 632 | 75 他就是整天愤愤不平OI制度...
愤世嫉俗
【在 e***e 的大作中提到】
: 某个当年的高中竞赛明星，保送复旦，后从复旦高调退学。等再次从网上看到这个名字
: ，俨然民科矣。
|
l***i
发帖数: 632 | 76 Well...combinatorics is a big class of unsorted maths... Thus there are all
kinds of problems, some need little knowledge, others need more advanced
tools.
When some part becomes mature, it would be removed from combinatorics and
form a new branch of mathematics... Just like algebraic topology...
or
understand
never
【在 e***e 的大作中提到】
: combinatorics today indeed uses many advanced techniques, like algebraic or
: analysis techniques. But it is still possible for a non-expert to understand
: a seminar of the subject or pick up a combinatorial problem, which is never
: gonna happen for those advanced-in-the-root areas like differential
: geometry or topology. In this sense, combinatorics still remains some user-
: friendly interfaces:)
|
l***i
发帖数: 632 | 77 通常是深刻的证明有价值
就像picard's theorem那种
有简单的证明
但是不如picard原来自己的证明那么penetrating...
所以一些书还是采用了picard的原来的麻烦的但是深刻的证明
太技巧化看起来很好
但是另一方面不是特别有价值
【在 e***e 的大作中提到】
: 我不懂你抬杠个什么劲，我本人就是CS理论和组合数学方向的，至少这个方向的大多数
: 人包括我都觉得being elementary是这个方向的特色。如果一个问题同时有初等证明和
: 非初等证明的话，通常初等证明都更有价值，除非那个非初等证明还能说明一些其他的
: 东西。否则也不会有"the book proof"这种说法。
: 我不明白你在跟我争什么。
|
f***y
发帖数: 218 | 78 又看到有关组合这个学科的讨论了。 记得当年有位学很高深（是真的）的数学的老兄
成天嘲笑组合， 甚至于在lovasz的讲座中大摇大摆的故意穿堂而过以示蔑视。。。当
然那时人家不识lovasz是何人。
楼上有位老兄说得很有理， 组合就是一些没法用大的理论解决的问题的‘理论’的方
法的集合， 真有理论了就不是组合了。 一些重要的不重要的问题没有任何大的理论可以应用的
时候， 也就只有初等的技巧了。 不是每个看起来初等的任何人都懂得东西就真的可以
挂以‘初等’的标签了的。说来惭愧，graph minor theorem的证明我就没全读懂， 据
我所知， 整个图论界可能也有多半人不懂。。。当然他们也不在意， 那里的技巧他们
多半也用不上。
Gowers就组合和其他理论驱动的数学写过一篇有意思的博文：The Two Cultures of
Mathematics。 读来还是挺有意思的。 他的老师有一多半是属组合的，所以他还真看
得挺透得。 呵呵 |
v********e
发帖数: 1058 | 79 上次水木吵这个话题的时候我贴过Gowers那篇文，根本没人看。说到底BBS就是吵架灌
水爽嘴皮子的地方，不能真正讨论问题。
可以应用的
【在 f***y 的大作中提到】
: 又看到有关组合这个学科的讨论了。 记得当年有位学很高深（是真的）的数学的老兄
: 成天嘲笑组合， 甚至于在lovasz的讲座中大摇大摆的故意穿堂而过以示蔑视。。。当
: 然那时人家不识lovasz是何人。
: 楼上有位老兄说得很有理， 组合就是一些没法用大的理论解决的问题的‘理论’的方
: 法的集合， 真有理论了就不是组合了。 一些重要的不重要的问题没有任何大的理论可以应用的
: 时候， 也就只有初等的技巧了。 不是每个看起来初等的任何人都懂得东西就真的可以
: 挂以‘初等’的标签了的。说来惭愧，graph minor theorem的证明我就没全读懂， 据
: 我所知， 整个图论界可能也有多半人不懂。。。当然他们也不在意， 那里的技巧他们
: 多半也用不上。
: Gowers就组合和其他理论驱动的数学写过一篇有意思的博文：The Two Cultures of
|
l******e
发帖数: 470 | 80 转过来看看，我看，呵呵。
【在 v********e 的大作中提到】
: 上次水木吵这个话题的时候我贴过Gowers那篇文，根本没人看。说到底BBS就是吵架灌
: 水爽嘴皮子的地方，不能真正讨论问题。
:
: 可以应用的
|
|
|
s*****g
发帖数: 5159 | 81 re,我也要看.
【在 l******e 的大作中提到】
: 转过来看看，我看，呵呵。
|
f***y
发帖数: 218 | 82 Here is the link: www.dpmms.cam.ac.uk/~wtg10/2cultures.pdf |
s*****g
发帖数: 5159 | 83 thanks.
【在 f***y 的大作中提到】
: Here is the link: www.dpmms.cam.ac.uk/~wtg10/2cultures.pdf
|
s**e
发帖数: 1834 | 84 Thanks. Good article.
【在 f***y 的大作中提到】
: Here is the link: www.dpmms.cam.ac.uk/~wtg10/2cultures.pdf
|
l******e
发帖数: 470 | 85 很不错的文章，顺便看了下Roth那篇文章(参考文献[R])，很精妙。
【在 f***y 的大作中提到】
: Here is the link: www.dpmms.cam.ac.uk/~wtg10/2cultures.pdf
|
