不确定性的困惑与NP理论分享 http://blog.sciencenet.cn/u/liuyu2205 平常心是道

博文

“NP理论”研究的缘起

已有 4520 次阅读 2015-1-5 22:42 |个人分类:不确定性问题和算法讨论|系统分类:科研笔记| NP理论, 计算复杂性理论, 求解NP-hard问题, 认识中西方文化

1993年,我在法国贡比涅大学(Université de Technologie de Compiègne)完成了计算机博士论文,步入了法国儒尔-凡尔纳大学(Université de Picardie Jules Verne)的教学和研究之路。法国大学的教学和科研体制,一方面,以其注重合作、富于个性的风格,使自己受益匪浅;另一方面,其强调程序性的教学模式,又让自己极不适应,加之语言的障碍,不禁困难重重,由此,却开启了自己重新认识中西方文化、实则认识自己之旅。那么,“NP理论”(这个概念以后再说明)的研究就是这段心路历程的写照。

具体说来,从事“NP理论”的研究,首先缘起于“计算复杂性理论(Computational Complexity Theory)”教学的“奇怪”经验。“计算复杂性理论”是众多的计算机基础课程的一部分,但是这部分的讲授,却令自己困惑不已,因为每次讲完后不久,首先是自己,就把讲授的内容几乎忘得一干二尽,只剩下几个形式化的定义:P,NP,NP-完备性,。。。

于研究,缘起于“启发式算法求解NP-hard问题”的困惑,虽然各种启发式算法层出不穷,呈百花齐放的景象,但却与“计算复杂性理论”隔山隔水,理论与实践严重脱节,自己不禁问为什么?。。。

直觉把自己引向了文化、思维认知,开始了寻师访友,。。。这一路走来,已是二十年!今天来到这里,是想和大家分享这段心路历程,同参共学,。。。



https://blog.sciencenet.cn/blog-2322490-856766.html


下一篇:Bill Gasarch关于“P versus NP”前途的二次调查
收藏 IP: 194.57.107.*| 热度|

1 杨正瓴

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-12-23 21:31

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部