我们继续和大家分享这次关于P vs NP讨论的第三部分，希望对此议题感兴趣的网友能对其中所蕴含的认知方面的问题有所思考。 我们的NP理论工作起于对流行NP定义的质疑和解读，在此基础上我们认为计算复杂性理论的“P问题”实际上就是可计算性理论的“可计算性问题（确定性问题）”，由此相对于P我们来认知NP，其定义自然为“不确定性问题（Nondeterministic Problem ）”。 如此针对Y君提出的“密码锁”问题，我们的观点也就与流行观点截然不同了，体现在讨论中就是与Y君观点的分歧，。。。 ＊＊＊＊＊＊＊ 黄岱永： 柳渝认为（这里所有的说法仅针对这个特定的密码问题）只要解的存在是可判定的，图灵机可求（精确）解的，那么可推演出P=NP。你无法证明这是错误的。所以有俗语说：天下没有绝对不可破译的密码（Cook有篇短文“The importance of the P versus NP question”其中有P vs NP与密码学的关系说明）。 正如Y君前所述，除了简单粗暴的穷举法外，我们也不能排除其它多项式时间内的破译密码算法。 实际上，如cook也意识到“一般来说，证明了诸如RSA之类的密码协议的安全性或DES比证明P ≠NP困难得多。”（In general, proving the security of cryptographic protocols such as RSA or DES is much harder than proving P ≠NP.）不仅基于离散量运算的密码学受到“P vs NP”问题的制约，就是连续量运算的密码学也受到实数环上的“P vs NP”问题的影响和制约。 正如图灵二战时期破译德军的密码，首先图灵判断德军的密码是存在的，因此他相信P=NP的（否则他不会徒劳而动的），也许一天前，这貌似是个不可能问题，但一天后，就已经解决。所以就此问题选择P问题不是错误的选择！(注意：我没说这是正确的选择，因为，真有可能破译不出来。） 至于柳渝定义的NP问题，我觉得还是比较清晰的，连解的存在都不可判定，那么显然没有求（精确）解的必然前提了，转而其次求图灵机近似解。从这里看来，密码问题显然不是柳渝定义下的NP问题。（但我觉得我还没有完全理解cook的思想，特别是其“hence bounded proof existence is in NP”有哪些内涵和外延 ？) G君： 看来从严格的数学公理也好，定理也好很难判断某一个组合问题的可求解性，不如反过来从实际已经求解成功的案例看，哪种组合可以求解，哪种组合必须要穷举法才能解。大规模集成电路的最短配线长，最小面积等的组合最佳化解的成功，用到了模块与模块之间的连结关系，通过由于存在着的连结关系而产生的概率信息，模块之间连结关系最密切的尽可能放在一起的规则，以及模块在相反的两个方向的对抗，从而获得最佳解，AlphaGo实际上也是利用了围棋的规则，人为的用程序进行的规则的堆积，再加上在出某一个棋子时的胜算概率，这个概率信息实际上也是由围棋规则产生的，以及双方的对抗，这个对抗的条件也是用程序进行规则的堆积的完善性，因此在组合问题上，各个要素之间是否有相关性是判断是否可进行最佳化解的判据。 柳渝： 黄岱永，你说 “只要解的存在是可判定的，图灵机可求（精确）解的，那么可推演出P=NP”，这样说的前提是认可NP的流行定义：“NP是NDTM多项式时间可求解”；如果不认可，P／=NP。 现在大家已经清楚关于NP的二种观点： 1，当前流行定义： －P是TM多项式时间可求解 －NP是NDTM多项式时间可求解；NP是TM多项式时间可验证 2，我们的定义： －P，确定性问题（等价于：解的存在可判定，图灵机可求（精确）解） －NP，不确定性问题（等价于：解的存在不可判定，图灵机可求（近似）解） 具体到密码锁，这二种观点导致： －密码锁是NP，如果能确定密码锁只有指数时间（O(2^N)）的“穷举法”求解； －密码锁是P，因为密码锁已经知道密码存在了，即“解的存在是可判定”的，图灵机可（确定性）求解。 大家会反驳我的“密码锁是P”的观点：这样一来岂不是说，所有的NP问题（如3SAT问题）都成了P，因为所有的NP问题都可“穷举法”求解。 实际上，求解密码锁与求解NP如3SAT的“穷举法”意义是不同的，表面上看都是“穷举法”，但是密码锁的搜索空间是O(2^N)，具有“线性结构”，使得机器的能力可以匹配问题规模的线性增长；而3SAT的搜索空间是比O(2^N)复杂得多，是“非线性增长”，机器的能力无法匹配问题规模的非线性增长，只能近似求解。 正是密码锁的“线性结构”体现了P的本质：“解的存在可判定”，而3SAT的“非线性结构“体现了NP的本质：“解的存在不可判定”。 我用一个例子图式说明密码锁与SAT的搜索空间（假设：密码是011，而3SAT公式的解也是011）： 所以，我们不同意NP的二个流行定义，根本原因就是NDTM的本质是TM（图灵机）： －“Every nondeterministic Turing machine has an equivalent deterministic Turing machine”－Sipser书中Theorem 3.16 NP的二个流行定义都让NP的本质“不确定性”消失了。 Y君： 你的想法基本讲清楚了。但是无法说服我。我想也无助于解决千禧年问题3。至于你是否能够说服学术界接受你的定义，我不知道，但是不看好。因为，你说的这些事情，大家都知道了几十年了。你并没有提供新的思路新的工具，完全仅是在定义上纠缠。可以这样看，即使学术界全面采用你的定义，我们对这些问题，是否有了进步？我看没有。 这里最关键的问题就是现在流行的NP表述：如果容易验证，是否容易求解？可以这样讲，为什么表述会逐渐演变成这个样子，其实正是因为这个样子反应了最本质的思想。这个问题成了千禧年问题3，就是科学家对此的反应。 你其实仅是在现有的NP里面再做分类：把那些不能够确知有解的再分出来。好啊。但是，这样分后，对我们有什么特别的好处呢？至少你还讲不清楚吧？ 即使如你所愿，定义中，把不确定性凸显出来，又能怎样？ 但是我很感谢你带来的讨论。虽然我不同意结论，但是讨论过程，以及过程中呈现出来的思路，乃至思绪苗头，都非常有趣，有帮助。我认为我收获很大。由衷感谢！ 话说到这里，遵循这个原则，思绪是更有趣的，我就来提问。可能有重要作用。 你讲： －但是密码锁的搜索空间是O(2^N)，具有“线性结构”，使得机器的能力可以匹配问题规模的线性增长；正是密码锁的“线性结构”体现了P的本质：“解的存在可判定”。 我想抓住这个问题讨论深入。请对这些话，做最详尽的解释。什么是线性结构？怎么增长机器能力？等等。我想你在这里面肯定思考过。但是从来没有看见你仔细写出来。 柳渝： 我们的讨论非常不容易，需要不断的学习和思考，所以不能着急。这里，我接着“密码锁”提一个问题： 问题：已知一个长度为m的数组A随机放置从0到m-1的整数，现给定一个0与m-1之间的整数a，问a在A中的位置。比如：A =5,A =1,A =3,A =0,A =4,A =6,A =7,A =2, 欲找整数6在A中位置。 既然m个整数是随机放置在A中的，也就是说，其放置没有任何规律，那么唯一的算法就是“穷举法”：枚举数组的元素，与a比较，最多比较m次，即可判定a在A中的位置。 比如，整数6在A中位置是i=5，即A =6。 现在问此穷举法的“算法（时间）复杂度”是什么？ Y君： 现在来说这个问题。这是很有名的搜索，叫什么名呢？我忘记了。其复杂度是log m。这没有问题，就是查查书就知道的。但是这个问题可以连接到密码锁吗？还联系不上。因为，放进数组，就已经给出了重大信息。而这个信息是密码锁不具备的。 柳渝： 这里因为没有任何关于数组里m个元素的排列信息，要找一个元素，就只能穷举搜索：从第一元素开始比较，最多比较m次，故算法复杂度是O(m)。 此穷举搜索的原理与你的密码锁开锁应该是一致的，你同意吗？ 这是有3个键的密码锁，假设密码是011，寻找密码开锁的过程示意图。你看有没有问题？ Y君： 没有问题。你已经用了最平凡的穷举。就是说，你认为对N长度的密码，搜索的难度是O(2^N)。这是我们一直在说的。 柳渝： 上面的穷举法的算法复杂度是O(m)，对应的问题是简单的数组搜索问题，一个公认的且显而易见的P问题。 现在令数组的长度m＝2^n，数组里的整数用二进制表达，比如上面的数组A放置2^3个二进制整数：A =101,A =001,A =101,A =000,A =100,A =110,A =111,A =010 穷举法的算法复杂度从O(m)变成了O(2^n)，那么是否就说原问题因此也就从P变成了NP？由此得出密码锁是NP？ 数组搜索问题从十进制变成二进制，参照系变了，计时的单位也变了，但问题本质却没变。就好比做一件事用了1小时，也可说用了60秒，但是不能说用60秒做的这件事，就变成了一个性质完全不同的事。 黄岱永： 涉及具体的算法时，相关信息在”算法与复杂性“的有关专著里基本都有详细的讨论。 Y君： 这个事情我就再说一次。 我们是从N位密码锁开始的。因此我们关心的是操作步数和N的关系。如N为3，平均要查找4次，N为4，平均查找8次，类推下去，如果N为100，平均查找（2^100）/2。对吗？那么，你怎么称呼这个规律呢？ 你考虑一个M维数组的搜索，其难度是O（M），这个肯定。没有任何争论。但是当M自身是幂呢？而且我们关心的是这个难度随指数的规律呢？ 柳渝： 记住我们的主题是：判断密码锁是P还是NP。 我前述分析是想表明，用穷举法的O(2^n)不能判断密码锁是P还是NP，反而会导致矛盾的结论。 因为这里涉及到对算法的“时间复杂度”的理解。在算法理论中，“时间复杂度”不是指算法求解问题的实际计算时间，而是指算法的计算能力对问题规模n的增长是否胜任，即“渐进时间复杂度O(f(n))”。 这里的关键是如何理解“问题规模n”？ 算法的“时间复杂度”针对二个层次的问题： 1，具体问题，比如：密码锁问题（如@岱永指出的） 2，P类或者NP类问题，比如：密码锁是P还是NP？ 就具体问题而言，“时间复杂度”是相对于同一问题来比较不同的算法的效率，同一问题的结构相同，所以只要设定一个表达“问题规模”的“数量”n，就可以在此基础上比较不同的算法。 比如：于密码锁，设n是锁位数，可以问：是否存在更有效的算法，其复杂度是O(n^k)？其实还可以设m是搜索空间，可以问：是否存在比O（m）更有效的算法？ 也就是说，针对具体问题的“时间复杂度”，仅仅是用数学意义上的“数量”n就可以表达“问题规模”，来比较求解同一问题的不同的具体算法。 但是就P或者NP而言，“时间复杂度”是相对于P与NP来比较二者的不同。由于具体问题有千差万别的结构，仅仅“数量”n不足以表达“问题规模”，而必须将问题的“结构”纳入“问题规模”的表达。 换句话说，针对P或者NP的“时间复杂度”，“问题规模”必须要反映问题在结构与数量的双重意义。 所以，我们分析密码锁：密码锁的n个锁位之间相互独立，不存在约束关系，故导致问题规模线性增长，而图灵机的计算能力也是线性增长，故我们认为密码锁是P问题。 Y君： 那么请给一个你对什么是P的严格定义。 柳渝： 图灵机可计算的（指可计算性），即可判定的、多项式时间复杂度（指问题规模线性增长）、问题具有线性结构，。。。这些都是一致性的表达。 Y君： 请给出精确严格定义。 黄岱永： 在上述我所说的三类定义下的第二类用法里，我觉得柳渝进一步说明了密码锁是P问题的问题，这个是很清晰的。特别强调的是“问题的线性规模的增长与图灵机 计算能力的线性增加的”的对应性，这个很重要。 实际上，从具体的算法来看，可以更加简化，因为密码锁是2的n次方个不相等的n位数的集合，可按大小排序，所以问题可转变为“求n个数中第k大数”(k不大于 n）的问题，用BFPTR算法，令密码数是数集中的第K大数即可，这样可以使算法的时间复杂度由最坏的O(n^2)变为O(n)，因此密码锁是一个P问题。 所以问题不是出自在算法上的，而是概念混乱导致的在P，NP以及NDTM,DTM的意义和层次上的歧义所致。 柳渝： Y君，P问题是图灵机可确定性求解的问题，在可计算性理论中由“可计算性”定义，在计算复杂性理论中由“多项式时间”（polynomial time，简记为P）定义。 黄岱永 你说的“求n个数中第k大数”(k不大于 n）的问题，好像与密码锁有别，因为关于密码锁的密码是没给出任何信息的，只能穷举或猜测。Y君，你同意吗？ Y君： 柳渝，你没有回答我的问题。我没有看到你的精确定义。如果我们没有一个明确的对象，就完全是在各说各话，没有有意义的交流。 我暂且不说任何其他的，等你的精确定义后，我们再说。 柳渝： Y君， “可计算性”的数学意义是“递归函数”。“可计算性”在可计算性理论中严格定义了的。 Y君： 你没有回答我的问题。 黄岱永： 柳渝， 1：密码锁的所有密码的集合是不是可以归结为2的n次方个n位数？2：由于每一个数是不等的，是不是可以排序？3：密码是不是上述集合中唯一的一个数？4：我们可不可以假设那个密码数在密码数集合里按序排在第k位？如果对以上四个问题的回答都是yes，那么就能用BFTPR算法。实际上是说，对于任一个有界有序数列集，求出其中任何一个（元）数的“中位数”算法的算法复杂度可以是O（n）。 我从我的观点来帮Y君回答，分三种情况讨论。特别地在定义一下，密码锁可以是NP问题。例如，A是上海人，我们说，A是中国人没错吧？这是P，NP的传统定义中即对立又包含的矛盾造成的。 柳渝： Y君，维基上关于P定义如下（https://fr.wikipedia.org/wiki/P_(complexité)）： Par définition, un problème de décision est dans P s'il peut être décidé par une machine de Turing déterministe en temps polynomial par rapport à la taille de l'entrée. On dit que le problème peut être décidé en temps polynomial. 这是我们认可的P定义。 柳渝： 黄岱永，Y君提出的密码锁问题是：不给开锁人任何信息，只知道有n个锁位，其值取0/1。 在此前提下，我来回答你的问题： 1：密码锁的所有密码的集合是不是可以归结为2的n次方个n位数？ 是。 2：由于每一个数是不等的，是不是可以排序？ 是。 3：密码是不是上述集合中唯一的一个数？ 是。 4：我们可不可以假设那个密码数在密码数集合里按序排在第k位？ 不能，因为你不知道k（k≤2^n）是什么，而这正是需要寻找的。 黄岱永： 实际都是在“猜”，中位数算法是两边同时向中间扫描的，猜到k位的时间相对较少。 柳渝： 我用Java编了一个模拟“穷举法”开密码锁的程序，程序非常简单，大家可以分析一下此程序复杂度。 public class Crypto { public static void main(String ); else { System.out.println(Number of bits must be provided as argument); return; } // print 2^n integers m = (int) Math.pow(2,n); System.out.println(Search a password in +m+ binarys); for (i=0; im; i++) { System.out.print(Integer.toBinaryString(i)+ ); } System.out.println(); // set a password x in x=(int)(Math.random()*m); // print this password System.out.println(); System.out.println(Set a password : ); System.out.println(Binary : + Integer.toBinaryString(x))； // serach this password i=0; stop = false; while (im stop!=true) { if (i==x) stop = true; else i++; } // print the found password System.out.println(); System.out.println(Find the password : ); System.out.println(Binary : + Integer.toBinaryString(i)); } } Y君： 我现在认为，关键在于密码锁这样的问题：搜索空间是2^N这样大，是否只能是穷举搜索？如果可以证明，基本上就证明了P不等于NP。如果能够证明总是能找到多项式搜索，基本上就证明了P等于NP。因此对这个问题的理解，就不仅仅是起认知模型的作用，而是最直接关联到核心。 说到多项式，2^N是N的指数函数，当然不是多项式。但是，如果m=2^N，那么m自然是m的多项式。但是这和定义已经违背了。P的定义中的多项式是定义为问题的尺度的多项式。密码锁的尺度是N，而不是2^N。 这些是非常初等的。在这些上面扯，实在没有任何意义。这是我感到讨论无法进行的原因。
标签: 密码锁
