[原创]NP完全问题的解法(续)[斑竹已阅]

我是01指挥员 收藏 6 1956
导读:根据S集(特征和)中符号的规律可以形成一种有效的算法,用来寻找或者判别出大的质数。本文得出的结论就是:NP完全问题可以得到解决,NP = P!
近期热点 换一换

3. 关于寻找或者判别大质数算法的探讨

利用S集(特征和)中符号的规律来寻找或者判别大质数,其实质内容实际上就是NP完全问题。这个问题涉及的内容非常重大,也极其复杂,无论是广度还是难度都很难用较短的篇幅就能够描述清楚。本文试图用一种简明的方式来进行探讨,定性地给出结论,希望能起到举一反三的作用。

虽然有关S集(特征和)的符号规律,作为一门崭新的理论显得还不够成熟;作为一条新开辟出来的数学研究道路,里面还有大量的工作有待于完善;作为一个整体,还没有系统地得到全面的证明。但是作者已经通过大量的实例进行了较为充分地验证,并且对于其中最为重要的那一部分,也就是立论的基础,猜测一、二的证明工作获得了进展。目前获得的阶段性成果,已经不会影响到如何根据S集中这些客观存在的符号规律,构成一种有效的算法,用来寻找或者判别质数,进入到实用性质的工程化应用阶段。作者想要着重指出,及早地开展工程上的应用,可以在某些特殊的领域里较快地产生重大成果。而且,这是一种在应用的过程当中,可以用传统公认的方法来进行验证的算法。

因为S集中符号规律的核心内容,就是“纵向循环、横向相乘”,所以运用S集中的符号规律来寻找或者判别质数,大致就可以有两条路径:根据正向定位法则一得到的S值符号纵向循环的规律,可从已获知奇(质)数O的S集,推断出新的奇(质)数O+2,S集中一部分相同位数上的S值;根据正向定位法则二以及猜测四和猜测五,仅仅从任意一个奇(质)数S集中少数已知的S值,直接推断出S集中其余全部未知的S值。

3.1 根据正向定位法则一以及S值的纵向循环规律来寻找或者判别质数

本文探讨的是一种全新的数学研究方法,它与过去传统的研究方法有着明显的不同之处。在一般情况下,我们是在得到了某个奇(质)数O以下所有质(奇)数的S集以后,再去研究O+2的S集,这是一种需要积累的方法,也正是所谓可带有记忆功能的特殊“筛法”的含义所在。在这个基础上,如果我们想要判别出一个新的质(奇)数O+2时,并不需要用筛法(或其它方法)重新把它再筛除(计算)一遍,也不需要重新计算每一个位数上余数R与正负符号或者标记N之间的对应规律。我们已经获知的奇(质)数O的S集中,各个位上的符号Sj,即Sj是否等于N,本身就是一个经过了筛法的结果,而且也曾经反复强调过,无论O+2等于何值均可套用,并不需要再二再三地重复计算。

根据在第2章中的讨论,可以把已经获得(积累)的某个奇(质)数O以下所有S集中每一位的符号Sj(类似于S集列表三),只分别与1(-1、+1)和N或者是“未知”,一一对应的关系设想成是一个“齿轮”。如果在每一位数上,Sj对应的循环周期长度有j个数(甚至更小),那么这个“齿轮”上就对应有着j个“齿”,如果奇(质)数O的S集中一共有O-1位S值,这部“数学机器”(数学模型)就一共有O-1个“齿轮”,并将随着奇(质)数的逐渐增大,S集中S值位数的增多而相应地增加。如果要得到一个新的奇数O+2的S集,并不需要分别地计算出每一位上的S值,应该对应的是在该位上,已可获知的符号循环周期中的哪一个符号。只需要将这部“机器”中的每个“齿轮”都同步地转动一步,利用S值符号周期循环的方法,就能够迅速地获知这个新的奇数O+2的S集中,大约三分之二位数上的S值符号Sj。根据在2.3一节中的讨论,假定已经获知了某个非常大的奇(质)数O,以及这个O值以下所有质数的S集和奇数的虚拟S集,并不意味着就能够得到这个奇(质)数O的S集中,所有位上S值的纵向循环规律。根据正向定位法则一,可以先得到奇数O+2的S集中,全部位数的大约三分之一位数上S值符号完整的循环规律,这些S值都是正向排序位于原S集中。然后根据拓展S集的定义,可以得到另外大约三分之一位于拓展S集中反向排序的S值。对于获得这些位于拓展S集中的S值,并不需要另外进行复杂的运算,只要把已经获得的位于原S集中正向定位的S值,在奇数O+2的拓展S集中,从最后一位,O+2-1位起反向排序即可。这就是为什么我们曾经在第2章中,要详细地讨论在S集中不同的位数上,S值符号的循环周期长度究竟有无规律,纵向循环周期的最大长度是多少,如何确定出最大可获知完整S值符号循环规律的位数j,以及最小未知S值的位数和最大未知S值的位数应该如何确定出来的缘故。这种方法,很容易地就能够通过计算机编程的方式来实现。

我们已经知道,判断出一个奇数是否为质数时的计算量,要小于计算出这个奇数S集中全部S值的计算量。如果我们只是想要知道一个新的奇数O+2是不是质数,而不是获取它的S集时,问题就变得更加简单了。正如我们曾经讨论过的那样,根据筛法我们已经知道了对于任何一个奇数O,只要它不含有小于√O的因子,就必然是个质数。而我们已经得到的奇数O的S集及其符号规律,本身就是个经过了“筛法”过程的结果。S集是由原S集和拓展S集共同组成,一共有O-1位,其中能够得出的完整S值符号循环规律的位数,有三分之一左右位于原S集中正向排序的位数较小的那部分, O–1/3要远远大于√(O+2)。比方说,要判断出奇数61是不是质数,按照筛法,当计算到61不能被7或11除尽时,就已经能判断出61是不是质数。而我们从59的S集中一共能够得到19位完整的纵向符号循环规律,因为位数19也是个质数,19*19 = 361。也就是说,采用这个方法,如果使得这部“数学机器”从O = 59开始,同步地转动k = 361-59 = 302步,只要新出现的每一个奇数的S集中,位数小于或等于19的所有S值都不出现N的标识,这个奇数就一定是个质数。使用这种方法可以象“印刷机”一样,连续不断快速地得到奇数361以下所有的质数,而不需要重复地使用筛法,分别对于所有小于361的奇数逐个地来进行判别。显然,采用本方法只需要极低的计算量,根据已获知的奇(质)数O的S集,就能够迅速地判断出新的奇数O+2,甚至是一个非常大的奇数O+k(k可以远远大于O),是不是质数。而且,k值与O是平方关系,可以粗略地用公式O^2/4^2 < k < O^2/3^2来对其进行估算。当奇数O足够大时,根据质数定理,从奇数O的S集中,能够得到最大质数位上的完整S值符号循环规律的位数,接近等于O–1/3,而新的非质数奇数O+k中最大的因子却不会大于√(O+k),所以可以假设O–1/3 = √(O+k),从而得知k值接近等于O^2/3^2。可见,奇数O越大,k就更大,这种算法的优势就越加明显。

经历了多少年来的努力,我们现在已经掌握的最大质数有一千多万位的长度,获取更大质数的难度将会越来越大。因此,人们才制造出一台又一台计算速度越来越快,容量也越来越大的巨型计算机,来克服因为计算方法所困而不能完成的任务。要是能够把一千万位长度以下所有奇(质)数的S集列表,都输入到计算机中去,根据k = O^2/3^2,就可以迅速地获得大致有二千万位长度以下的所有质数。

3.2 根据正向定位法则二以及猜测四和猜测五来寻找或者判别质数

正如曾经在“S集(特征和)的符号规律”一文中,所举出的例十三、例十四、例十五和例十六那样,根据正向定位法则二以及猜测四和猜测五,实际上它们已经可以构成一个完整的算法,略加改进后就可以单独用来寻找或者判别质数。不过目前还存在着二个问题:一是对于猜测四、五的证明尚未解决,但这显然不应该影响到,如何应用这种算法来解决实际问题,除非发现了反例。第二点就是正向定位法则二以及猜测四、五,只是在理论上认为可以,但并没有具体地给出对于任意一个奇(质)数,应该如何来计算出它全部S值的通用方法。虽然作者现在已经能够具体地给出这种算法,并且又进行了大量的计算和验证,但是在猜测四、五被证明出来之前,在这个算法当中又会产生出一些新的猜测,作者不愿意猜测六、猜测七地继续下去。主要原因是在大量的计算和验证的基础上,经过进一步分析后发现,即使是单独地应用正向定位法则二能够构成一种算法,也可以获得S集中全部的S值,但是它并不能成为一种最优的算法。所以,因为篇幅和实用价值的缘故,本文不准备详细地介绍这种算法,只要知道“只用S2和S3(S3≠N)两个S值,根据正向定位法则二以及拓展S集的定义,任意一个质数S集中所有的S值,都能够被推算出来”这种结论即可。

3.3 两种算法可合并为一种最优算法

即使是上述这两种算法,都可以单独作为一种算法来解决大质数的识别问题,但是在识别质数或者是获取一个新的奇数O+2的S集的问题上,这两条路径却各有长处,而优劣刚好可互为补充。正向定位法则一,描述的是S集中同一位数上S值符号的纵向循环规律。这种算法的优点在于,可以积累并且应用那些已经计算出来的S值符号纵向循环规律,快捷地判别出新的质数,并且得到新的奇数O+2,S集中大约三分之二位上的S值。而正向定位法则二,描述的是S集中S值符号之间横向相乘的关系,长处在于计算过程简单快捷,可用于计算出,在应用S集符号的纵向循环规律时得不到的那小部分S值。

显然,寻找或者判别质数时的最优路径,即计算量最小的方法,应该是把分别基于正向定位法则一和正向定位法则二而形成的这两种算法,取长补短地结合起来。寻找或者判别一个新的奇数O+2及其S集的具体算法如下:

如果已知某一个奇数O以下所有奇数的S集(虚拟S集),并不意味着就得到了这个奇数S集中所有位上S值的循环规律,只能是根据正向定位法则一和拓展S集的定义,按照3.1一节中给出的方法,可先得到奇数O+2的S集中,总位数的大约三分之二位上的S值。

对于其中未能得到的那小部分S值,应用正向定位法则二,只需要较小的运算量,就能够迅速地从已知的S值推算出所有这些未知的S值。正如我们在2.3一节中已经讨论过的,根据S值符号循环规律可获知的S值的位数是从1到j,有大约三分之一是位于原S集的前部,另外三分之一位于拓展S集的最后部分。而未知S值的位数,是在从j+1到2*(j+1)-2、2*(j+1)-1或2*(j+1)之间。未知S值的个数始终都是偶数,有一半位于原S集中,另一半位于拓展S集中。最小未知S值的位数j+1乘以2,要大于或者等于最大的未知S值位数。在一般情况下,只需要把位于原S集中任意一个未知S值的位数乘以2,通过S2*(j+1) = S2*Sj+1、S2*(j+2) = S2*Sj+2这类的运算,即可从位于拓展S集中已知的S值,推算出任意一个未知的S值。如果未知S值的最大位数刚好等于2*(j+1)时,这唯一一个用正向定位法则二无法推算出来的S值的情况,也正是在2.3一节中已经讨论过的,最小的未知S值位数乘以2,刚好等于最大的未知S值位数,这就意味着新的奇数O+2必然含有3和j+1的因子,它一定不是个质数。只要事先判断出是否有S3 = N(为了降低计算量,在对算法进行计算机编程时,这种判断可以不用对奇数O+2除以3的方法,而用S3周期循环的方法即可),就可以提前获知是否有Sj+1 = S2*(j+1) = N。

最妙的就是,为了降低求出上述那小部分未知S值时的计算量,还可以有更加快捷的方法,不一定需要采取S2*(j+1) = S2*Sj+1、S2*(j+2) = S2*Sj+2这类的计算,来逐个地确定出每一个未知S值的位数及其对应的已知S值。在规定了S集中所有不带有N标记的S值,也就是+1或-1都可以被认为是1的情况下,必然会有S2 = 1。因为未知S值的个数始终都是偶数,有一半位于原S集中,另一半位于拓展S集中,除去我们已经讨论过的,最小未知S值的位数j+1乘以2,刚好等于最大的未知S值位数2*(j+1)的情况,其余的全部位于原S集中的未知S值,刚好就等于我们已经根据拓展S集的定义而获知的,位于拓展S集中全部偶数位上的S值。它们之间,不仅仅是需要根据正向定位法则二来进行计算的关系,还可以是免于计算就能够直接一一对应出来的关系。

例如,根据在2.3一节中的讨论,41的S集中未知S值的位数是14——27,一共有14个未知的S值。其中的一半,第14——20位7个未知S值是位于原S集中,因为S2恒等于1,而且S3 ≠ N,所以S14——S20就分别等于(对应)拓展S集中已知的全部偶数位上的7个S值,S28——S40。

例如,45的S集中未知S值的位数是15——30,一共有16个未知的S值。因为S3 = N,最小未知S值的位数15乘以2,等于最大的未知S值位数30,所以可以提前获知S15 = S30 = N。其余未知S值的位数是16——29,其中的一半,第16——22位7个未知S值是位于原S集中,因为S2恒等于1,所以S16——S22就分别等于(对应)拓展S集中已知的全部偶数位上的7个S值,S32——S44。

其余位于拓展S集中未知的S值,可以根据拓展S集的定义,对应地从原S集中刚刚获知的S值中直接获取。

这样我们就以极低的计算量,获取了新奇数O+2的S集中全部的S值。

3.4 最优算法的特点以及对于计算量的评估

通过上述两个大的运算步骤,把两种算法取长补短地结合起来,我们获得了一种最优的算法,可以快捷地获知任意一个奇数O+2的S集中全部S值。获取一个新的奇数O+2的S集,尤其是获得S集中所有标记为N的S值位数,要比判别出它是否是一个质数更加重要,计算量也将更大,但同时也为获取下一个新的奇数O+4的S集,做好了准备工作。

这种算法主要的特点就是,尽量避免不必要的数字之间的计算,尽量通过逻辑判断的方法,来直接获取(读取)奇数O+2的S集中每一位上的S值。这种根据S集的符号规律来寻找或者判别质数的算法,比起传统的筛法有三个明显的优点:

一、它是一种可带有记忆功能的方法。从应用正向定位法则一的计算步骤上看,获得S集的过程也是一种可以剔除所有非质数奇数的“筛法”,不过这种“筛法”和我们以前判别质数时所使用过的筛法明显有所不同,它是一种特殊的“筛法”。在过去的方法中,如果要判别出一个新给出的奇数P+2是不是质数,即使是在判定质数P时已经对它进行过一次筛法,但是在传统的数字结构体系下,因为它是一种基于数的筛法,而P和P+2是两个不同的数,所以此时仍然需要重新再筛除一遍。这就是现用所有方法的通常弊病,也是造成寻找大质数的过程,随着数字的增大,变得越来越极其困难的主要原因。而根据S集的符号规律,是可以把数字的结构,分解成由若干位有规律可寻的符号所组成的S集(特征和),再按照这种数字的新结构S集去研究数。一旦确定出了S集列表中,同一位数上的S值符号纵向的循环规律,尤其是标记N的循环规律以后,它们就不会再发生变化,可以用S集列表的形式记录下来,并且对于所有的质(奇)数都适用,这是一种基于“位”的“筛法”。虽然P和P+2仍然是两个不同的数,但它们S集中S值个数的多少只是略有不同,在S集中相同位数上的S值符号,循环规律都是相同的,无论P为何值时均可套用。即使是对于一个新给出的奇数P+2,甚至是P+ k,也没有必要重新计算那些已经计算过的,S集中相同位数上Sj的符号变化规律,可以根据已知的S值符号循环规律,得知Sj是否等于N,就能够迅速地判断出它是否是质数,并直接获取大部分位上的S值。而且,待判别的奇数O越大,这种方法的优点就越明显,这就是建立起S集这种数字新结构概念后的精妙之处。

二、因为S集中的S值都只是一些符号甚至就是1,即使是需要根据正向定位法则二来计算其中一部分未知S值时的运算,实际上也只不过是一些符号之间的运算。例如,进行Sj = S2*Sk,Sk = S2*Sj,S2 = Sj*Sk这一类的乘除运算,实际上仅仅是一些符号之间的运算而已。这种仅限于符号之间进行运算的计算量,同样是一次乘除运算,要比起在应用筛法时,质数P动辄为上千万位长度的天文数字之间的一次乘除运算,完全可以忽略不计。

三、它是一种利用S集中的符号规律来进行推算的算法,是一种不需要在数字之间进行复杂计算的算法。它可以在符号规律的基础上,通过某种相互对应的逻辑关系,来直接获取新的奇数未知的S值,这就是这种算法的计算量将会很小的原因。它首先从奇数O的S集中,根据S值的纵向循环规律,对应地获知新的奇数O+2的S集中大约三分之二位上的S值;剩下的三分之一未知S值中的一半,可从已获知的拓展S集中全部偶数位上的S值,一一对应地直接获得;其余六分之一位于拓展S集中未知的S值,可以根据拓展S集的定义,再对应地从原S集中获取。这种算法非常适合采用计算机编程的方式来实现。

这种综合地应用S集中特有的符号规律而形成的算法,对于计算机在空间上的复杂性要求相对来说并不大,大约在P^2的量级。因为这种新方法有别于传统的方法,是否能够满足对于时间上的复杂性(Complexity)要求,也就是计算量的大小,要作出准确的定量分析有些困难,不过定性地估算是可能的。在一般情况下,我们是在得到某个质数P以下的所有S集以后,再去研究P+2的S集。如果仅仅是为了判断出新的奇数P+2,甚至是P+k以下所有的奇数是否为质数(k可以远远大于P),根据3.1一节中给出的方法,计算量也只是大约在O(P)的量级,不会超过O(P^2)。即使是为了获取一个新的奇数P+2的S集,根据3.3一节中给出的方法,保守地估算,计算量也不过是大约在O(P^2)的量级,不会超过O(P^3)。完全能够满足解决NP完全问题中,对于P问题的多项式公式计算量的要求。因此得出的结论就是:NP完全问题可以得到解决,NP = P!


参考文献

华罗庚,数论导引,北京,科学出版社,1957,7,178-181页。

李联林,关于质数的充分必要条件的猜测,中国科技论文在线,2009年4月3日。

http://www.paper.edu.cn/paper.php?serial_number=200904-102

李联林,S集(特征和)的符号规律,中国科技论文在线,2009年4月6日。

http://www.paper.edu.cn/paper.php?serial_number=200904-142


The Solution for the NP Completeness Problem

Li Lianlin

Abstract

The author of the paper uses one kind of effective algorithm which based on the rules of signs in S Set(Character Sum) to recognize and seek out the large prime numbers with less computation. The conclusion from this paper is that NP Completeness is solved, NP = P!

Keywords: elementary number theory, prime number, trigonometric sum, character sum, NP completeness

本文内容于 2009-8-19 1:03:51 被zhao2365192编辑

1
回复主贴

相关推荐

更多 >>
聚焦 国际 历史 社会 军事 精选
6条评论
点击加载更多

发表评论

更多精彩内容

热门话题

更多

经典聚焦

更多
发帖 向上 向下