[原创]数学第一难题NP完全问题的解决路径

数学第一难题NP完全问题的解决路径

The Solution of NP-Completeness

李联林


摘 要: 本文通过对两篇数学论文的总结,探讨了只需要较小的计算量就可以进行大质数识别的路径,得出了数学界公认的七大数学难题之一,NP完全问题已经解决的结论。

关键词:NP完全问题 七大数学难题 多项式公式 质数 素数 三角和 特征和

NP完全问题是当今数学界公认的七大数学难题之一,这七大难题是:NP完全问题 、霍奇猜想、庞加莱猜想、黎曼假设、杨-米尔斯理论、纳卫尔-斯托可方程、BSD猜想。在数学领域里众多亟待破解的难题和名目繁多的猜测中,经过美国克雷数学研究所的科学顾问委员会精心挑选出来的这七大难题,都有着同样的特点:不但是极其深邃难解,而且一旦在这些问题的获解上哪怕是获得了些许的进展,就将对数学理论的发展和应用产生极其巨大的推动作用。研究这些“千年大奖问题”已经成为世界数学界的热点,不少国家的数学家正在组织联合攻关,同时它们也是任何一个数学工作者都梦寐以求予以摘取的数学皇冠上的耀眼明珠。可以预期,这些“千年大奖问题”将会改变新世纪数学发展的历史进程。有意思的是,在这七大难题中排在首位的NP完全问题,在名称上就有别于其它六个问题,也是其中唯一一个不是用人名来命名的数学难题。因为它不是某个数学家火花一闪、灵机一动所提出的理论或是猜测,而是一个非常古老的问题,涉及到了最基础的数学理论,并且经过了几百年来无数数学家们持之以恒的努力,直到现在仍然是一个没有得到解决的公开问题。对于这样一个在数论中占有极其重要地位的课题,或许是因为久无进展的缘故,以至于有人开始怀疑它是否真的存在,现在学术界就有一些专家倾向于认为这样的一个多项式或是函数根本不存在([德]U.杜德利. 基础数论[M],P23. 周仲良译. 上海:上海科学技术出版社,1980)。NP完全问题包含着两部分的内容:P(多项式算法)问题和NP(非多项式算法)问题,但核心问题还是用于质数判别的多项式公式算法问题。通俗地讲就是究竟有没有可以用来判别任意一个奇数是不是质(素)数,同时计算量又比较小的公式。严格地讲计算这种多项式公式或是函数的算法必须满足对于算法的复杂性(Complexity)上的要求,而公认的有实用价值算法的计算量应该为O(P^k)(其中P是某个质数,k是任意一个常数)。

本人撰写的“有关质数与三角函数关系的猜测”以及“特征和(S集)的符号规律”这两篇论文(用任意一种搜索软件在网上都可以搜索到),基本上就可以构建起一条完整的NP完全问题的解决路径。在这里我想着重指出的是,这种NP完全问题的解决路径,是一种全新的方法,是建立在大跨度地发展了数论中的三角和理论、特征和理论的基础上,才成为可能。

“有关质数与三角函数关系的猜测”这一篇论文,以全新的形式给出了质数的必要条件(一个多项式公式),并首次提出了特征和(S集)是可以采用排列组合的方式,代入这个必要条件中计算出来的论断。尽管在此阶段它的计算量还是很大,但这已经使得利用一个新的多项式公式来判断出,任意一个奇数是不是质数成为可能。同时,特征和(S集)的表达形式,又会给人耳目一新的感觉,多少也能使人联想到“杨辉三角形”的精髓和数学所特有的那种内在的美。

在“在特征和(S集)的符号规律”这篇论文中,又进一步探索出了特征和(S集)的符号规律,其实质就是:不同的奇(质数)在相同的特征和位数j上具有相同的符号循环规律。建立起了一个完整的运算法则体系,只需要较少的计算量就可以得到一个新的奇(质)数的特征和(S集),这就意味着NP完全问题的获解,能够判断出任意一个奇数是否为质数的多项式公式逐渐成为现实。论文中的[例十二],表述了在已经获知某个奇(质)数P的特征和(S集),以及所有小于这个数的奇数的特征和(包括虚拟S集)基础上,如何只需要很少的计算量,就可以迅速地得到一个新的奇(质)数P+2的特征和(其实质是得到了新的位数j上的符号循环规律)。而论文中的[例十三],则描述了如果获知了一个新的奇(质)数P+2的特征和,如何再经过较少的计算量,就能迅速地判断出这个新的奇(质)数P+2,甚至P+k是否为质数。这个过程的计算量相对来说并不大,应该在有实用价值的O(P^k)的计算量以下,能够满足对于算法的复杂性(Complexity)上的要求,但准确的结论还是由计算数学工作者来作出评断为好。在现阶段,这个数P是不是我们已知的最大质数暂时并不重要,只要在计算量不大并且小于O(P^k)的情况下,能够得到一个多项式公式,可以用来判断一个新的奇(质)数P+2甚至P+k是不是质数即可。

根据以上的论述,我认为NP完全问题已经获得解决。


附:NP完全问题的简单表述

在一个周六的晚上,你去参加一个盛大的晚会。由于感到局促不安,你想知道在这一大厅中是否有你认识的人。如果没有人提示,你就必须环顾整个大厅,去一个个地审视每一个人,看看是否有熟人(这就好比是数学中的筛法)。要是主人向你提示说,那位正在甜点盘附近的罗丝女士一定是你所认识的朋友,不费一秒钟,你就能向那里扫视,并且发现你的主人是正确的。这就是现实生活中具有普遍现象的一个例子,生成问题的一个解(答案)通常要比验证一个给定的解所花费的时间多得多。与此类似的是,如果某人告诉你,一个其实并不太大的数13,717,421可以写成两个较小的数的乘积,你可能不知道是否应该相信他,但是如果他告诉你这个数可以因式分解为3,607乘上3,803,那么你用一个袖珍计算器就可以轻易地加以验证。对于一个未知的疑难问题,不管我们编写的计算程序是多么的灵巧,判定一个答案的正确与否是可以很快地利用已有的知识来验证的,如果没有这样的提示就需要花费大量时间来求解,它被看作逻辑和计算机科学中最突出的问题之一。这是斯蒂文•考克于1971年陈述的(本人略加修改)。


本文内容为我个人原创作品,申请原创加分

[ 转自铁血社区 http://bbs.tiexue.net/ ]

猜你感兴趣

更多 >>

评论

评 论

更多精彩内容

新闻阅读排行

热门图集