评论:挖“地雷”能挖出百万美金吗
http://www.sina.com.cn 2000/11/15 09:05 北京青年报
您知道吗,平时为打发时间才玩的“扫雷”游戏能够解决P对NP这一悬赏百万美金的“千禧”数学难题,日前,英国伯明翰大学数学教授凯伊公布了这一线索,不过,清华大学计算机系黄连生教授认为,解决“千禧难题”需要更新的数学概念,而不是在现有理论上大量运算。
据悉,凯伊教授是在偶然接触到“扫雷”游戏后蹦出这一想法的,他表示:“我一向对带有数学要素的游戏感兴趣,数学和游戏是存在默契的,我突然想到在‘扫雷’后面可能有一个很棒的数学原理,如果把它放在一个更大的格子图中来玩,并决定所有地雷组合的运算,就可能解出P对NP这一难题,这样一来像计算机密码这类问题就可迎刃而解。”而美国麻省克莱数学学院已将P对NP问题和另外六个难题一起并列为“千禧难题”,还准备了100万美金奖金。
记者从清华大学计算机系黄连生教授处了解到,“P对NP是一个运算复杂性问题,它试图判定一些我们在短期内看似无法解决的问题,实际上存在一个相当简单的解决办法,只是尚未被我们发现。目前,我们熟知的P对NP问题就有几百个,扩展起来就更多了,因此如果P对NP问题解决了,全世界的数学家和计算机学家都要放假三天”。
不过黄教授表示:“凯伊教授的解法只是存在可能,如果将格子放到无限大的话,从排列组合的角度讲很可能造成指数爆炸,而无法算出结果,至于密码问题,即使是P对NP问题解决了也无法破解像量子密码这样的计算机密码,所以我认为,解决‘千禧难题’需要更新的数学概念,而不是在现有理论上大量运算。”(本文采写樊宏)
|