|
|
NP完全问题的解法
李联林
摘 要：根据S集（特征和）中符号的规律可以形成一种有效的算法，用来寻找或者判别出大的质数。本文得出的结论就是：NP完全问题可以得到解决，NP = P！
关键词：初等数论 质数 三角和 特征和 NP完全问题
1.引言
作者在“关于质数的充分必要条件的猜测”的论文中，给出了一组新型的质数充分必要条件，首次提出了可以通过全取排列的方式计算出质(奇) 数的S集（特征和），使得可以把数字的结构分解成由若干位符号所组成的S集（特征和）。在S集这种新的数字结构体系下，任何一个质数都已不再是不可拆分的基本单元，而可以用一组有规律可寻的正负符号来描述，这将导致一种崭新的数学研究方法诞生。既可以用传统公认的方法来验证这种体系的正确性，又可以从中得到一系列有新意的学术成果。“关于质数的充分必要条件的猜测”一文中给出的猜测一和猜测二，就是建立起这种创新的数学研究方法的基础。
作者又在“S集(特征和)的符号规律”的论文中，创立了适用于非质数奇数的虚拟S集（虚拟特征和），进一步得到了任意一个质（奇）数的S集（特征和）中，任意一位的符号Sj都是有规律可寻的结论。通过一系列的符号法则以及猜测四、五，把看似杂乱无章的S值（特征值）符号全部都有规律地联系在一起。无需采用全取排列的方法，仅仅需要较小的计算量就能够求出任意一个质（奇）数的未知S集，从而可以快捷地判断出任意一个奇数，S集中的S值是否带有N的标记。这样就给质数的识别带来极大的方便，并给七大数学难题之一，NP完全问题(NP Completeness)的解决带来新的思路。
NP完全问题之所以能够排在七大数学难题之首，不但是因为它有着极大的理论价值并且非常难解，而且一旦被破解以后，在众多的工程领域里还可以得到广泛的应用。经过斯蒂芬.库克（Stephen A. Cook）等许多数学家的努力，目前已经发现大约有四千多个问题可以列为NP完全问题，例如：汉弥尔顿回路问题（Hamiltonian cycle problem）、旅行推销员问题（Traveling salesman problem）、布尔可满足性问题（Boolean satisfiability problem）（SAT）等等。但是，所有这些问题相互之间都有一个共同的特点，即可以归约（Reduction）。只要针对其中某个特定的NP完全问题找到了一种算法，所有的这类问题都可以迎刃而解，因为他们都可以转化为同一个问题。
历史悠久的质数判别问题就是NP完全问题中的核心问题。在历史上，这个问题曾经吸引了包括费马（Fermat）、欧拉（Euler）、勒让德（Legendre）和高斯（Gauss）在内的大批数学家，花费了大量的时间和精力去研究这个问题。几百年来，对于这个问题持之以恒地研究，极大地推动了数学理论的发展。NP完全问题是由P(Polynomial)问题和NP（Non-Deterministic Polynomial）问题两部分组成。P问题的核心，就是究竟有没有可以用来推算出质数，同时计算量又比较小的多项式公式。严格地讲，计算这种多项式公式或是函数的计算量，必须满足对于算法的复杂性（Complexity）上的要求。公认的有实用价值的算法，计算量应该为O(P^c)，其中c可以是任意一个常数，但是越小越好。如果无法得到这种多项式公式，那就导致了NP问题，即非多项式算法问题。NP问题的核心就是究竟有没有一种算法，同样可以在多项式时间以内，用来判别出任意一个奇数是不是质数，给出我们所需要的答案。这就是著名的数学难题，NP = P？ 目前绝大部分的学者倾向于认为NP ≠ P，一个关键的原因就是经过数十年来的研究，没有人能够发现一个NP完全问题的多项式时间算法。而且，在NP完全的概念出现之前，人们早就已经开始寻求这种算法了。再进一步地讲，如果得出了NP = P这样的结论，还会导致很多惊人的结果，而这些结果现在被大多数学者相信是不成立的，但又无人能够证明出来它们并不成立。
比如，众所周知的公钥密码的理论基石，就是建立在NP完全问题难解性的基础上发展起来的。如果针对NP完全问题能够找到一种有效的解法，那么目前正在广泛使用的绝大多数RSA公开密钥码体制，将面临着崩溃的危险，因为RSA体制与质数的判别有着密切的联系。
无论如何，只要能够给出一个NP = P的相关算法，或者是证明出来NP ≠ P，NP完全问题都能够算是获得解决。本文在上述两篇论文的基础上，在S集这种崭新的数字结构体系下，根据破解出来的S值符号之间的规律，另辟蹊径形成了一种崭新的有效算法，可以用来寻找或者判别大质数，使得NP完全问题获得解决。
2.正向定位的S值符号纵向循环周期
我们已经知道，在包括所有奇数的S集列表中，S集中符号规律的核心内容，简单地说就是“纵向循环、横向相乘”。因此，研究S集中S值符号纵向的循环规律，就占有着重要的地位。本章所要讨论的是，在已经获知的奇（质）数O的S集列表中，其中任意一位上 S值符号纵向的循环周期长度究竟是多少，如何通过尽可能小的符号循环周期，根据正向定位法则一，可以推算出新奇数O+2的S集中同一位上的S值符号。关于S值符号纵向的循环周期问题，已在“S集（特征和）的符号规律”一文的第2章中有所讨论，但还不够系统和完整。它与寻找和判别质数的最优算法有着密切的联系，所以有必要全面地把这种S值符号的纵向循环规律进一步总结、归纳、提高。
2.1 正向定位S值符号的纵向循环周期长度
我们已经知道，在奇（质）数O的S集{S1 … Sj … So-1}当中，一共有O-1位S值。当Sj的位数j是质数，j ≡ 3（mod 4），或者当j = 2、3、7、11…时，在该位上S值符号一个完整的循环周期中有2 * j个数，是个偶数，同一位数上相隔一个循环周期的S值相互之间必然是同号，相隔半个循环周期的S值必然是反号。因此，我们可以利用半个循环周期之间相互对应的S值符号相反的特点，最小仅用半个循环周期的长度j个数，即可推断出新的奇（质）数S集中同一位数上的S值符号Sj。
当位数j也是质数，但是j ≡ 1（mod 4），即位数j = 5、13、17…时，在这些位数上，一个完整的S值符号纵向循环周期的长度是j个数。不同奇数的S集，在同一位数上相隔一个循环周期的S值，相互之间必然是同号，不过在这些位数上不存在半个循环周期的概念。
当位数j为合数时，假设j = 2 * 3 * 4 * … * k（其中k可以是某个因子的多次方），根据正向定位法则二，可有Sj = S2 * S3 * S4 * … * Sk。在该位数上S值符号Sj循环周期的情况就稍微复杂些，其中既有相同因子的平方关系，也有不同因子之间的相乘关系。在该位上，S值符号Sj在S集列表中纵向排列的循环周期，是它的位数互质的S2 、S3 、…、Sk各自循环周期长度的最小公倍数。因为这些S值的位数k，既有k ≡ 1（mod 4），循环周期为k个数的情况；也可以有k ≡ 3（mod 4），循环周期为2 * k个数，但是循环周期的前后半个周期相互对应位上符号相反的情况。所以，在任意一个合数位j上S值循环周期的长度，既可以有j个数（甚至更小）；最大的循环周期长度也可以有 2 * j个数，但前后半个循环周期相互对应位上的符号相反。
综上所述，S集中任意一位数j上 S值符号的纵向循环规律，可供利用的的最小周期长度不超过j个数，由此可得出的结论就是：对于任意一个位数j上的S值，只要相隔j个数，就一定能推断出在相同位数上的下一个S值符号。
这个结论可以在S集列表一、二中得到充分地验证。例如位数6的S值循环周期，是它的因子2和3各自循环周期4、6的最小公倍数12，循环的S值符号为：-1，N，-1，+1，N，+1；+1，N，+1，-1，N，-1，一共有2 * j = 12个数，但是前后半个周期相互对应位上的符号相反，所以可供利用的的最小周期长度为6个数。位数10的循环周期，是它的因子2和5各自循环周期4、5的最小公倍数20，循环的S值符号为：-1，-1，N，+1，-1，+1，-1，N，+1，+1；+1，+1，N，-1，+1，-1，+1，N，-1，-1，一共有2 * j = 20个数，前后半个周期相互对应位上的符号相反，所以可供利用的的最小周期长度为10个数。位数15的循环周期，是它的因子3和5各自循环周期6、5的最小公倍数30，循环的S值有2 * j = 30个数，前后半个周期符号相反，所以可供利用的的最小周期长度为15个数。
S值符号纵向循环周期长度：
S值位数j 完整循环周期长度 是否有前后半个
周期符号相反 循环的S值
2 4 (2*j) 是 -1,+1；+1,-1
3 6 (2*j) 是 -1,N,+1；+1,N,-1
4 1 否 +1
5 5 (j) 否 +1,-1,N,-1,+1
6 12 (2*j) 是 -1,N,-1,+1,N,+1；
+1,N,+1,-1,N,-1
7 14 (2*j) 是 -1,-1,+1,N,-1,+1,+1；
+1,+1,-1,N,+1,-1,-1
8 4 是 +1,-1；-1,+1
9 3 否+1,N,+1
10 20 (2*j) 是-1,-1,N,+1,-1,+1,-1,N,+1,+1；
+1,+1,N,-1,+1,-1,+1,N,-1,-1
11 22 (2*j) 是 -1,+1,-1,-1,-1,N,+1,+1,+1,-1,+1；
+1,-1,+1,+1,+1,N,-1,-1,-1,+1,-1
12 6 是+1,N,-1；-1,N,+1
13 13 (j) 否+1,+1,-1,-1,+1,-1,N,-1,+1,-1,-1,+1,+1
不过，若要利用S值符号纵向循环规律的最小周期长度，来推算出下一个S值的正负符号，还需要根据是否有j ≡ 1、3（mod 4），来分别判别出在每一个位数j 上，S值完整的循环周期长度究竟应该是j个数还是2 * j个数，然后才能够确定出在它的循环周期中，是否存在着前后半个周期符号相反的情况，仍然太麻烦，会增加很大的计算量。在下一节中，将寻找出更好的方法来解决这个难题。
2.2 S集中寻找或者判别质数的关键是标记N
在S集列表中可以发现，即使是在某个位数j上，S值符号的最大循环周期为2 * j个数，而且在前后半个循环周期中，相互对应位上的符号相反，但是标记N却始终是没有正负之分的S值。所以，在任意一个位数j上，对于标记N而言，它的循环周期的最大长度只有j个数。
我们已经知道，根据S集的符号规律，来寻找或者是判别任意一个奇数O是不是质数时，关键之处是看这个奇数的S集中，S值是否带有N的标记。至于在其余的位数上，S值究竟是+1还是-1并不关键，而且这些正负符号，只是在验证计算结果是否正确时才有用。但是，对于一个有着上千万位长度的质数，要把它S集中天文数字般的S值，都代入到猜测一给出的三角和公式中去进行验证，既无必要也不可行。所以，可以在已经获知的S集的符号规律中，把所有不带有N标记的S值，也就是+1或-1都认为是1，只要保持标记 N在非质数奇数的虚拟S集中，位数及其循环规律不变即可。这样做的简化规定不会带来任何影响，反而是在推断计算时更加简单，更加贴近寻找和判别质数这个问题的实质。建立起可以适用于非质数奇数的虚拟S集以后，改变了应用传统的三角和、特征和理论研究质数时的惯用思维方式，它不是刻意地去研究质数的特征值是什么，而是着重研究在什么样的情况下奇数就不会是个质数。所以说，获取任意一个奇数S集中S值符号的规律，以及能够判别出质数的关键之处，是获取虚拟S集中标记N的位数规律。
随着对于S集中客观存在的符号规律认识上的加深，从最初的只包括质数的S集列表，逐渐演变成了含有非质数奇数虚拟S集的S集列表一，含有拓展S集的S集列表二，直到S值不再分为正负的S集列表三。S集列表经历了由简到繁，再由繁到简的不断演变，内涵也得到了一次次的升华。再进一步，还可以考虑把S集列表三中的拓展S集简化掉，甚至把合数位上的S值也进行简化，这样就可以进一步减少算法的计算量，但因为对结论无重大的影响，所以本文暂不对此展开讨论。从寻找或者判别质数的角度上讲，S集中符号的规律，实际上已经逐渐脱离了数论中原有的三角和、特征和的概念，演变成了一种新型的，只讨论虚拟S集中标记N位数的规律。这样一来，对于正向定位法则一、二的证明，将逐渐变得清晰可行。
S集列表的获取将变得更为简单：所有质数S集中的S值都等于1；所有非质数奇数的虚拟S集中，仅有与奇数因子有关的位数上的S值等于N，其余的S值也都等于1。某一位数j上的S值Sj等于1的含义有两点：该S值的位数j一定与奇数O互质（参见猜测五），如果某个奇数S集中所有的S值都等于1，不带有N的标记，同样可以说明这个奇数是个质数；在应用正向定位法则二时位数j可参与运算，用于推算出其它位数上的S值，尤其是其它带有N标记的S值的位数。
在这种对于S值的特殊选定情况下，对于“任意一个位数j上的S值，只要相隔j个数，就一定能推断出在相同位数上的下一个S值符号”的结论，可以修改为更加简明扼要：对于任意一个位数j上的S值，只要相隔j个数，就一定能推断出在相同位数上的下一个N标记。这就是根据S值，尤其是质数位上标记N的S值循环规律，能够判别出新质数的关键之一。
例如S集中位数6上的S值，S6的循环周期，可以被认为不超过6个数（实际上还可以更小，但这已经足够了），循环的S值符号为：1，N，1，1，N，1。位数10上的S值循环周期，不超过10个数（实际上只有5个数），循环的S值为1，1，N，1，1，1，1，N，1，1。位数15的S值循环周期，不会超过15个数。而且在任意一个位数j上，都不再有前后半个周期相互对应位上的符号相反的概念，所以无需对下一个S值的符号正负做出判断，这样计算量就可以被大大降低。
S集列表三：
P = 3， S ={1；1}
P = 5， S ={1，1；1，1}
P = 7， S ={1，1，1；1，1，1 }
O = 9， S ={1，1，N，1；1，N，1，1}
P = 11，S ={1，1，1，1，1；1，1，1，1，1}
P = 13，S ={1，1，1，1，1，1；1，1，1，1，1，1}
O = 15，S ={1，1，N，1，N，N，1；1，N，N，1，N，1，1}
P = 17，S ={1，1，1，1，1，1，1，1；1，1，1，1，1，1，1，1}
P = 19，S ={1，1，1，1，1，1，1，1，1；1，1，1，1，1，1，1，1，1}
O = 21，S ={1，1，N，1，1，N，N，1，N，1；1，N，1，N，N，1，1，N，1，1}
P = 23，S ={1，1，1，1，1，1，1，1，1，1，1；1，1，1，1，1，1，1，1，1，1，1}
O = 25，S ={1，1，1，1，N，1，1，1，1，N，1，1；1，1，N，1，1，1，1，N，1，1，1，1}
O = 27，S ={1，1，N，1，1，N，1，1，N，1，1，N，1；1，N，1，1，N，1，1，N，1，1， N，1，1}
P = 29，S ={1，1，1，1，1，1，1，1，1，1，1，1，1，1；1，1，1，1，1，1，1，1，1，1，1，1，1，1}
P = 31，S ={1，1，1，1，1，1，1，1，1，1，1，1，1，1，1；1，1，1，1，1，1，1，1，1，1，1，1，1，1，1}
O = 33，S ={1，1，N，1，1，N，1，1，N，1，N，N，1，1，N，1；1，N，1，1，N，N，1，N，1，1，N，1，1，N，1，1}
O = 35，S ={1，1，1，1，N，1，N，1，1，N，1，1，1，N，N，1，1；1，1，N，N，1，1， 1，N，1，1，N，1，N，1，1，1，1}
P = 37，S ={1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1；1，1，1，1，1， 1，1，1，1，1，1，1，1，1，1，1，1，1}
O = 39，S ={1，1，N，1，1，N，1，1，N，1，1，N，N，1，N，1，1，N，1；1，N，1，1，N，1，N，N，1，1，N，1，1，N，1，1，N，1，1}
P = 41，S ={1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1；1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1}
P = 43，S ={1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1；1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1}
O = 45，S ={1，1，N，1，N，N，1，1，N，N，1，N，1，1，N，1，1，N，1，N，N，1；1， N，N，1，N，1，1，N，1，1，N，1，N，N，1，1，N，N，1，N，1，1}
P = 47，S ={1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1；1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1}
O = 49 S ={1，1，1，1，1，1，N，1，1，1，1，1，1，N，1，1，1，1，1，1，N，1，1，1；1，1，1，N，1，1，1，1，1，1，N，1，1，1，1，1，1，N，1，1，1，1，1，1}
O = 51，S ={1，1，N，1，1，N，1，1，N，1，1，N，1，1，N，1，N，N，1，1，N，1，1， N，1；1，N，1，1，N，1，1，N，N，1，N，1，1，N，1，1，N，1，1，N，1，1，N，1，1}
P = 53，S ={1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1， 1，1，1；1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1}
O = 55，S ={1，1，1，1，N，1，1，1，1，N，N，1，1，1，N，1，1，1，1，N，1，N，1，1，N，1，1；1，1，N，1，1，N，1，N，1，1，1，1，N，1，1，1，N，N，1，1，1，1，N，1，1，1，1}
O = 57，S ={1，1，N，1，1，N，1，1，N，1，1，N，1，1，N，1，1，N，N，1，N，1，1， N，1，1，N，1；1，N，1，1，N，1，1，N，1，N，N，1，1，N，1，1，N，1，1，N，1，1，N，1，1，N，1，1}
P = 59，S ={1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1， 1，1，1，1，1，1；1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1}
P = 61，S ={1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1；1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1，1}
（S集由原S集和拓展S集两部分组成，列表中黑体字为原S集，红体字为拓展S集。）
2.3 任意一个奇数S集中能够被推算出来S值符号完整循环周期的最大位数j
在第3章中将要讨论，如何根据正向定位法则一获得的S值符号的纵向循环规律，尤其是标记N的纵向循环规律，用作辨别质数时的一种算法。所以，确定出能够从已经获知的奇数O及其以下所有质（奇）数的S集中（例如S集列表三），可以获得原S集中完整S值符号循环规律的最大位数j，以便用于求出新的奇数O+2原S集中相同位数上的S值，就非常重要。它与新的奇数O+2的关系，分三种不同的情况可用三个公式来表达：
当j为奇数时，O + 2 = 3*j +2；
当j为偶数时，0 + 2 = 3*j + 1，或0 + 2 = 3*j + 3 = 3*（j+1）。
奇数O+2能够从奇数O的S集中，被推算出来S值符号完整循环周期的位数列表：
奇数O+2 用于推算循环周期
的起始S值 可获知完整循环周期
S值的最大位数j 未知S值
的位数 最大未知S
值的位数 已知S值对应在
拓展S集中的位数
41 = 3*j+2 15的S13 1——13 14——27 2*（j+1）-1 28——40
43 = 3*j+1 15的S14 1——14 15——28 2*（j+1）-2 29——42
45 = 3*（j+1） 17的S14 1——14 15——30 2*（j+1） 31——44
47 = 3*j+2 17的S15 1——15 16——31 2*（j+1）-1 32——46
49 = 3*j+1 17的S16 1——16 17——32 2*（j+1）-2 33——48
51 = 3*（j+1） 19的S16 1——16 17——34 2*（j+1） 35——50
53 = 3*j+2 19的S17 1——17 18——35 2*（j+1）-1 36——52
55 = 3*j+1 19的S18 1——18 19——36 2*（j+1）-2 37——54
57 = 3*（j+1） 21的S18 1——18 19——38 2*（j+1） 39——56
59 = 3*j+2 21的S19 1——19 20——39 2*（j+1）-1 40——58
61 = 3*j+1 21的S20 1——20 21——40 2*（j+1）-2 41——60
63 = 3*（j+1） 23的S20 1——20 21——42 2*（j+1） 43——62
从表中可知，任意一个新的奇（质）数O+2，能够从已经获知的奇（质）数O的S集中，利用S值符号纵向的循环规律，推算出它的S集中接近三分之二位上的S值。
例如，从表中可知奇数45，最多能够从43以下的S集列表中，获得14位完整的符号循环规律。因为位数14的S值循环周期的长度是28个数，但前后半个周期符号相反，所以只要14（j）个数即可。用于推算原S集中，可获知符号循环周期最大位数j的起始S值，是从奇数17的S14开始，经过14（j）个数的循环周期，到43的S14为止。因为对于O、O+2、O+4…等不同的奇数，在S值符号不分正负的S集列表三中，原S集中的S值对应到拓展S集，可分别有SO-j = Sj、SO+2-j = Sj、SO+4-j = Sj …。所以，根据拓展S集的定义，S45-j = Sj，对应到拓展S集中还可以获知另外的14个S值，位数是31到44，所以剩下的未知S值的位数只是从15到30。
从上表中可以发现，因为任意一个奇数O的S集中，S值的个数始终都是偶数O-1，所以未知S值的个数也就只能是个偶数。最小未知S值的位数是j+1，最大未知S值的位数可以有分别等于2*（j+1）-2、2*（j+1）-1和2*（j+1）三种情况，最小未知S值的位数j+1乘以2，要大于或者等于最大的未知S值位数。如果j是个奇数，最大未知S值的位数等于2*（j+1）-1（例如上表中的41、47、53、59）；如果j是个偶数，最大未知S值的位数可以分别有等于2*（j+1）-2（例如上表中的43、49、55、61），和2*（j+1）（例如上表中的45、51、57、63）两种情况。当j为偶数，且0 + 2 = 3*j + 3 = 3*（j+1）时，新的奇数O+2必然含有3和j+1的因子，它就一定不是个质数，就会出现最小的未知S值位数j+1乘以2，刚好等于最大的未知S值位数2*（j+1）的情况，此时必有Sj+1 = S2*（j+1） = N。
例如O +2 = 45，当可知的S值循环周期最大位数j为14是个偶数，未知的S值最小位数为15时，根据公式可有0 + 2 = 3*（j+1），43 + 2 = 3*15，45的S集中未知S值的最小位数是15，未知S值的最大位数是30，3和5刚好就是45的因子，所以有S15 = S30 = N。
从上表中可以得知，只要任意一个奇数不含有3的因子，即S3≠N，它未获知的S值最小位数是j+1，最大的未知S值位数就只能是2*（j+1）-2和2*（j+1）-1这两种情况之一，而不可能是2*（j+1）。最小未知S值的位数j+1乘以2，要大于最大的未知S值位数。这个结论对于3.3一节中进行的讨论极为有用。
通过研究S集列表可以发现，S集中奇质数位上第一次出现N的标识的最小奇数，都是0+2 = 3*（j+1）这一类的非质数奇数。刚好都是从已经获知的奇数O及其以下所有质（奇）数的S集中，可获知完整循环周期S值的最大位数j是个偶数，最小未知S值的位数j+1乘以2，等于最大的未知S值位数2*（j+1），因此有Sj+1 = S2*（j+1） = N。例如，非质数奇数9的S集中S3 = N，非质数奇数15的S集中S5 = N，非质数奇数21的S集中S7 = N，它们都是S集列表中，第一次出现新的质数位上有N标识的最小奇数。随着0+2的增大，j+1将覆盖所有的奇数，虽然它不一定是个质数，不过所有大于2的质数都在其中。这就是为什么从有限的奇数O的S集列表中，按照一种特定的算法规律，可以无限制地获得越来越大的非质数奇数0+2，S集列表中越来越多新的质数位上出现N标识的原因。而这种在新的质数位上不断出现N标识的现象或是规律，恰恰就是在3.3一节中所探讨的，能够不断地寻找或者判别出更大质数时的关键之处。
最大可知S值的位数j以及最大未知S值的位数，都是按照奇、偶、偶，有规律、有节奏地变化着，这种奇偶循环周期的长度是3个数。在对于算法进行计算机编程时，可以利用这种位数的奇偶循环变化规律，来减少需要确定出某一个S值位数时的计算量。
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 |
|
IP卡
狗仔卡
发表于 2009-8-14 17:06
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
楼主