|
|
| 空间结构计算机与NP完全问题 |
|
|
|
|
空间结构计算机与NP完全问题
求解或判定一个答案是否可以利用有关知识很快验证？或是没有任何捷径而花费大量时间求解？这是多项式复杂程度的非确定性问题。是世界七大数学难题之首简单的表述是NP=P?。
我们认为P类问题是有确定性算法的问题，NP类问题是有没有确定性算法或有最优解的问题；NPC类问题则是有确定解都不知道的问题。这不是等于不等于的问题，而是集合的类属问题。如P类问题是在整数集范围内，用加减运算就能完全解决的问题。NP类问题是在有理数集合范围内，用乘除运算才能完全解决的问题如1/7，只要得出0.142857（一个6位小数循环周期），就可判定它有任意精确值，不用再进行计算。也能用6＋1＝7判定7是否质数（6是1/7的小数循环周期）。虽然质数不能都用这种办法判定，但这是有效的判定方法之一。NPC类问题是在实数集范围内用乘方开方、对数反对数运算才能完全解决的问题。如2的平方根，是个不确定性问题不能。
P≠NP？真的就成了世界难题，如果分清楚不同的非确定性类，不是相等关系，而是相容关系。就像整数集相容于有理数集，有理数集相容于实数集……，直接就可确定整数集≠有理数集≠实数集。反过来实数集≠有理数集≠整数集。因为整数集不包括循环小数，有理数集不包括无限不循环小数。
说P=NP本身就是一个误导人的不严谨问题，基于计算机，多相式的复杂存在不确定问题，判定问题的复杂性不等于求解问题的复杂性。好的算法可以减少计算时间，但那是最优化问题。P类计算机，解决或判定一个NP问题，因与所解问题不同构，必然有一个算法最优化的问题。无解就成了NPC类问题（如无限不循环小数）。如果有NP类问题找到了确定的最佳算法，那它就不再NP类问题P≠NP？P类集合、NP类集合、NPC类集合都具有开放性，解决P类问题也不能穷尽计算，也有计算时间不能忍受的问题。优化问题、搜索问题、定理证明、航空公司的最佳线、破解密码……无论你多么聪,都不能算法。是一个问题可否被计算机描述并解决？执行一个给定的算法需多长时间?所需时间与问题规模有何函数关系？实质是解题算法最优形式化上限？计算机解题能力上限？NP类计算机的问题！
从系统论的角度讲，自然界不存在两个完全相同的系统，且总是高级系统相容低级系统，低级系统不能相容高级系统，P≠NP。如基于整数因子（P集）构造的系统属P类系统；就没有基于有理数因子（NP集）构造的NP类系统复杂。假设这是两种类型的计算机，前者肯定没有后者复杂，计算能也没后者强大。但它同样P≠NP。
假如以二进制与十六进制计算机说明这一问题，二进制计算机就是P类计算机，它的一位只有0、1两个因子，是P类集合，N位则是2的N次乘方。用三位二值码表达的数值是8。十六进制计算机则是NP类计算机，它的一位有0－15个因子，是NP类集合，N位则是16的N次乘方。用二值码表达需12位，表达的数值是4096。比三位二值码多四倍。可数值却大了512倍！可见其外延大多了。如果是计算机，其计算能力是指数级增加，计算时间指数级减少。不管是证明、判定或求解各类问题，都将大大减少用于求解的时间，也会降低求解问题的复杂性或不确定性。
计算的实质是输入状态的逻辑关系等于输出状态，因为集合的类属不同，相对于输出的确定性，输入不确定，或输入有确定性，而输出不确定的情况比比皆是，如1/7、2的平方根等，这是计算复杂性的由来。用二进制计算机计算十进制数时，还有个算法的转换问题。进制的不同，计算机的效率与计算复杂性有大的差别，这也是提出NP=P?问题的内在原因。解决它的最终结果多项式复杂程度的是设NP类计算机NP类。
至于能否构造NP类计算机？答案是肯定的。事实上人们探索高阶计算机，如量子计算机我们依据空间结构计算理论构造出的16进制计算机，就属NP类计算机。
设计新型NP类计算机，主要的阻力来自状态的确定二进制计算机之所以能够实现，是因为它基于两种状态就可实现十进制计算必须要体现十种状态，但其实不然，基于空间计算理论，状态关系可不由逻辑关系而由空间位置确定，值态可由编译码器确定，这就是我们能够设计出空间结构计算机的根本原因。
设计出NP类计算机，肯定能使所解问题简化，所用时间减少，能降低问题的计算复杂性，甚至使某类不能解决的问题得以解决。但与P类计算机属于两个不同的集合，不能改变P≠NP的现实。但这一问题可以转换为另一个问题计算机的计算能力有限制吗？能否构造出超越图灵机的类脑计算机？能构造出NP类或NPC类计算机吗？这一问题已涉及到自然科学最基础最核心的理论问题。单纯从计算的角度讲，并非只是基于量子计算才能构成NP类计算机，量子状态的确定及操作有先天的不足！基于空间结构计算理论构造空间结构计算机是必然选择！
NP类计算机之所以能够减少用于解决，是以自身的复杂性为代价的。并非P类计算机的复杂性。P≠NP的事实不能改变。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
