2006 年,我在博客(当时还是 MSN Space)上发了 《什么是 P 问题、NP 问题和 NPC 问题》 一文。这是我高二搞信息学竞赛时随手写的一些东西,是我的博客中最早的文章之一。今天偶然发现,这篇现在看了恨不得重写一遍的“科普”竟仍然有比较大的阅读量。时间过得很快。《星际争霸》(StarCraft)出了续作,德国队 7 比 1 大胜东道主巴西,《学徒》(The Apprentice)里的那个家伙当了总统,非典之后竟然出了更大的疫情。现在已经是 2022 年了。这 16 年的时间里,我读了大学,出了书,娶了老婆,养了娃。如果现在的我写一篇同样话题的科普文章,我会写成什么样呢?正好,我的新书《神机妙算:一本关于算法的闲书》中有一些相关的内容。我从书里的不同章节中摘选了一些片段,整理加工了一下,弄出了下面这篇文章,或许能回答刚才的问题吧。
有一天,我和老婆去超市大采购。和往常一样,结完账之后,我们需要小心谨慎地规划把东西放进购物袋的顺序,防止东西被压坏。这并不是一件容易的事情,尤其是考虑到各个物体自身的重量和它能承受的重量之间并无必然联系。鸡蛋、牛奶非常重,但同时也很怕压;毛巾、卫生纸都很轻,但却能承受很大的压力。于是,我突然想到了这么一个问题:给定 n 个物体各自的重量和它能承受的最大重量,判断出能否把它们叠成一摞,使得所有的物体都不会被压坏(一个物体不会被压坏的意思就是,它上面的物体的总重小于等于自己能承受的最大重量)。
事实证明,这是一个非常有趣的问题——老婆听完这个问题后整日茶饭不思,晚上做梦都在念叨着自己构造的测试数据。这里,我们不妨给出一组数据供大家玩玩。假设有 A、B、C、D 四个物体,其中:物体 A 的自重为 1,最大承重为 9;物体 B 的自重为 5,最大承重为 2;物体 C 的自重为 2,最大承重为 4;物体 D 的自重为 3,最大载重为 12。在这个例子中,安全的叠放方式是唯一的,你能找出来吗?
答案:C 在最上面,其次是 B,其次是 A,最下面是 D。注意,在这个最优方案中,最上面的物体既不是自身重量最小的,也不是承重极限最小的,而是自身重量与承重极限之和最小的。事实上,最优方案中的四个物体就是按照这个和的大小排列的!对于某种叠放方案中的某一个物体,不妨把它的最大载重减去实际载重的结果叫作它的安全系数。我们可以证明,这种按自身重量与载重能力之和排序的叠放策略可以让最危险的物体尽可能安全,也就是让最小的那个安全系数达到最大。如果此时所有物体的安全系数都是非负数,那么我们就相当于有了一种满足要求的叠放方案;如果此时仍然存在负的安全系数,那么我们就永远找不到让所有物体都安全的叠放方案了。
假设在某种叠放方案中,有两个相邻的物体,上面那个物体的自身重量和最大载重分别为 W1 和 P1,下面那个物体的自身重量和最大载重分别为 W2 和 P2。再假设它俩之上的所有物体的重量之和是 W,这是这两个物体都要承担的重量。如果 W1 + P1 大于 W2 + P2,那么把这两个物体的位置交换一下,会发生什么事情呢?原先下面那个物体的安全系数为 P2 − W − W1,移到上面去之后安全系数变成了 P2 − W,这无疑使它更安全了。原先上面那个物体的安全系数为 P1 − W,移到下面后安全系数变成了 P1 − W − W2,这个值虽然减小了,但却仍然大于原先另一个物体的安全系数 P2 − W − W1(这里用到了 W1 + P1 > W2 + P2 的假设)。因此,交换两个物体之后,不但不会刷新安全系数的下限,相反有时还能向上改进它。
所以说,我们可以不断地把自身重量与载重能力之和更小的物体换到上面去,反正这不会让情况变得更糟。最终得到的最优方案,也就与我们前面给出的结论一致了。
为了解决某类问题,我们经常需要给出一个策略,或者说一个方案,或者说一个处理过程,或者说一系列操作规则,或者更贴切的,一套计算方法。这就是所谓的“算法” (algorithm)。
让我们来总结一下。我们的问题是:给定 n 个物体各自的重量,以及每个物体最大可以承受的重量,判断出能否把它们叠成一摞,使得所有的物体都不会被压坏。它的算法则是:按照自身重量与最大承重之和进行排序,然后检验这是否能让所有物体都不被压坏,它的答案就决定了整个问题的答案。有了算法后,实际的计算过程一般就会交给计算机来完成的。程序员的工作,就是编写代码,把算法告诉计算机。
让计算机把每个物体的自身重量和最大承重加起来,这好办。如果有 n 个物体,那就要算 n 遍加法。给它们排序的时候,我们要依次做下面这些事情:
- 把 n 个数逐一过一遍,找出最小的那个数(n 次操作)
- 把最小的那个数放到第 1 个位置(1 次操作)
- 把剩下的 n − 1 个数逐一过一遍,找出最小的那个数(n − 1 次操作)
- 把最小的那个数放到第 2 个位置(1 次操作)
- ……
这要用 n + 1 + (n − 1) + 1 + … + 1 + 1 = (n2 + 3n) / 2 次操作。物体从上到下该怎么摆,现在就知道了。为了检验有没有东西被压坏,则需要把物体的重量从上到下累加一遍,边加边要和下一个物体的承重做比较。考虑到最上面的物体不用做检验,操作次数姑且就算 2(n − 1) 吧。这样的话,整个算法需要 (n2 + 9n) / 2 − 2 次操作。当然,在编写程序时,一些细节处可能还需要很多额外的操作。不过,对于运算速度极快的计算机来说,这都可以忽略不计。
计算机动辄处理成千上万的数据,多那么一两次操作不会从根本上影响整个处理过程的开销。为了评估处理数据的效率,我们更应该关注总操作次数的“级别”。我们甚至可以把 (n2 + 3n) / 2 次操作、(n2 + 9n) / 2 − 2 次操作以及 2n2 + n + 1 次操作、10n2 − 13n + 500 次操作等等,统统都叫作“操作次数以 n2 的级别增长”,它们都代表着同一个意思:当 n 很大的时候,如果 n 变成了原来的 k 倍,那么总的开销大致就会变成原来的 k2 倍。1894 年,德国数学家保罗·巴赫曼(Paul Bachmann)提出了一种使用起来非常方便的“大 O 记号”(big O notation),用到这里真是再适合不过了。如果某个函数 f(n) 的增长速度不超过 n2 的级别,那么我们就可以记下 f(n) = O(n2)。因而,随着 n 的增加,(n2 + 3n) / 2 、(n2 + 9n) / 2 − 2 、2n2 + n + 1 、10n2 − 13n + 500 的增长速度都可以用 O(n2) 来表示。类似地,n3 / 10、(n3 + 3n) / 2、10n3 − 6n2 + 100 则都相当于 O(n3)。
完成刚才那个算法需要的操作次数是 O(n2) 级别的。假设每次操作耗时相同,那么运行这个算法所需要的时间也应该是 O(n2) 级别的。更专业的说法则是,整个算法的“时间复杂度”(time complexity)为 O(n2)。1985 年由英特尔公司推出的 80386 芯片每秒钟可以执行 200 万个指令,1999 年的英特尔奔腾 III 处理器每秒钟可以执行 20 亿个指令,2012 年的英特尔酷睿 i7 处理器每秒则可以执行 1000 亿个以上的指令。不妨假设,当 n = 10 的时候,借助上述算法,计算机只需要 0.1 毫秒就能得到答案。算法的时间复杂度为 O(n2),说明当 n 增加到原来的 100 倍时,运行完成所需的时间会增加到原来的 10000 倍。因此,如果 n 变成了 1000 时,计算机也只需要 1 秒就能得到答案。即使 n 增加到了 100000,计算机也只需要 10000 秒就能得到答案,这大约相当于 2 个小时又 47 分钟。
其实,为了判断出这些物体能否安全叠放,我们似乎完全不必如此煞费心机。我们还有一个更基本的方法:枚举所有可能的叠放顺序,看看有没有满足要求的方案。n 个物体一共会产生 n! 种不同的叠放顺序,每次检验都需要耗费 O(n) 的时间。所以,为了得到答案,最坏情况下的时间复杂度为 O(n · n!)。那么,我们为什么不采用这种粗暴豪爽的算法呢?主要原因大概就是,这种算法的时间复杂度有些太高。但是,既然计算机的运算速度如此之快,O(n · n!) 的时间复杂度想必也不在话下吧?让我们来看一看。仍然假设 n = 10 的时候,计算机只需要 0.1 毫秒就能得到答案。令人吃惊的是,若真的以 O(n · n!) 的级别增长,到了 n = 15 的时候,完成算法全过程需要的时间就已经增加到了 54 秒。当 n = 20 时,算法全过程耗时 1.34 亿秒,这相当于 1551 天,也就是 4.25 年。当 n = 30 时,算法全过程耗时 700 万亿年,而目前的资料显示,宇宙大爆炸也不过是在 137 亿年以前。如果 n = 100 的话,计算机需要不分昼夜地工作 8.15 × 10140 年才能得到答案。根据目前的宇宙学理论,到了那个时候,整个宇宙早已一片死寂。
为什么 O(n2) 和 O(n · n!) 的差异那么大呢?原因就是,前者毕竟属于多项式级的增长,后者则已经超过了指数级的增长。
指数级的增长真的非常可怕,虽然 n 较小的时候看上去似乎很平常,但它很快就会超出你的想象,完全处于失控状态。一张纸对折一次会变成 2 层,再对折一次会变成 4 层……如此下去,每对折一次这个数目便会翻一倍。因此,一张纸对折了 n 次后,你就能得到 2n 层纸。当 n = 5 时,纸张层数 2n = 32;当 n = 10 时,纸张层数瞬间变成了 1024;当 n = 30 时,你面前将出现 230 = 1 073 741 824 层纸!一张纸的厚度大约是 0.1 毫米,这十亿多张纸叠加在一起,也就有 10 万多米。卡门线(Kármán line)位于海拔 100 千米处,是国际标准规定的外太空与地球大气层的界线。这表明,把一张纸对折 30 次以后,其总高度将会超出地球的大气层,直达外太空。
波斯史诗《王书》记载的故事也形象地道出了指数级增长的猛烈程度。一位智者发明了国际象棋,国王想要奖赏他,问他想要什么。智者说:“在这个棋盘的第一个格子里放上一颗大米,第二个格子里放上两颗大米,第三个格子里放上四颗大米,以此类推,每个格子里的大米数都是前一个格子的两倍。所有 64 个格子里的大米就是我想要的奖赏了。”国王觉得这很容易办到,便欣然同意了。殊不知,哪怕只看第 64 个格子里的大米,就已经有 263 ≈ 9.22 × 1019 颗了。如果把这些大米分给当时世界上的每个人,那么每一个人都会得到上千吨大米。国际象棋的棋盘里幸好只有 64 个格子。如果国际象棋的棋盘里有 300 个格子,里面的大米颗数就会超过全宇宙的原子总数了。
因而,在计算机算法领域,我们有一个最基本的假设:所有实用的、快速的、高效的算法,其时间复杂度都应该是多项式级别的。因此,在为计算机编写程序解决实际问题时,我们往往希望算法的时间复杂度是多项式级别的。这里的“问题”一词太过宽泛,可能会带来很多麻烦,因而我们规定,接下来所说的问题都是指的“判定性问题”(decision problem),即那些给定某些数据之后,要求回答“是”或者“否”的问题。
在复杂度理论中,如果某个判定性问题可以用计算机在多项式级别的时间内解出,我们就说这个问题是一个 P 问题,或者说它属于集合 P。这里,P 是“多项式”的英文单词 polynomial 的第一个字母。之前那个叠放东西的问题,就是一个 P 问题。
历史上至少有过两个问题,它们看起来非常困难,非常不像 P 问题,但在人们的不懈努力之下,最终还是成功地加入了 P 问题的大家庭。其中一个是线性规划(linear programming),它是一种起源于二战时期的运筹学模型。1947 年,乔治·丹齐格(George Dantzig)提出了一种非常漂亮的算法叫作“单纯形法”(simplex algorithm),它在随机数据中的表现极为不错,但在最坏情况下却需要耗费指数级的时间。因此,很长一段时间,人们都在怀疑,线性规划是否有多项式级的算法。直到 1979 年,人们才迎来了线性规划的第一个多项式级的算法,它是由前苏联数学家列昂尼德·哈奇扬(Leonid Khachiyan)提出的。另外一个问题则是质数判定问题(primality test):判断一个正整数是否是质数(prime),或者说判断一个正整数是不是无法分成两个更小的正整数之积。人们曾经提出过各种质数判定的多项式级算法,但它们要么是基于概率的,要么是基于某些假设的,要么是有一定适用范围的。2002 年,来自印度理工学院坎普尔分校的阿格拉瓦尔(M. Agrawal)、卡亚勒(N. Kayal)和萨克斯泰纳(N. Saxena)发表了一篇重要的论文《PRIMES is in P》,给出了第一个确定性的、时间复杂度为多项式级别的质数判定算法,质数判定问题便也归入了 P 问题的集合。
同时,我们也有很多游离于集合 P 之外的问题。互联网安全高度依赖于一种叫作 RSA 算法的加密体系,里面用到了非常犀利的一点:在整数世界里,合成与分解的难度是不对等的。任意选两个比较大的质数,比如 19 394 489 和 27 687 937。我们能够很容易计算出它俩相乘的结果,它等于 536 993 389 579 193;但是,如果反过来问你,536 993 389 579 193 可以分解成哪两个质数的乘积,这却非常难以迅速作答。把一个大整数分解成若干个质数之积,这就是著名的“整数分解问题”(integer factorization problem)。目前,人们还没有找到一种快速有效的整数分解算法。也就是说,目前人们还不知道整数分解问题是否属于 P。(这里我们指的也是整数分解问题的判定性版本,即给定一个正整数 N 和一个小于 N 的正整数 M,判断出 N 是否能被某个不超过 M 的数整除。)人们猜测,整数分解很可能不属于 P。这正是 RSA 算法目前足够安全的原因。
另一个著名的问题叫作“子集和问题”(subset sum problem):给定一个整数集合 S 以及一个大整数 M,判断出能否在 S 里选出一些数,使得它们的和正好为 M?比方说,假设集合 S 为
{38, 71, 45, 86, 68, 65, 82, 89, 84, 85, 91, 8}
并且大整数 M = 277,那么你就需要判断出,能否在上面这一行数里选出若干个数,使得它们相加之后正好等于 277。为了解决这类问题,其中一种算法就是,枚举所有可能的选数方案,看看有没有满足要求的方案。如果我们用 n 来表示集合里的元素个数,那么所有可能的选数方案就有 O(2n) 种,检验每一种方案都需要花费 O(n) 的时间,因而整个算法的时间复杂度为 O(n · 2n)。虽然人们已经找到了时间复杂度更低的算法,但没有一种算法的时间复杂度是多项式级别的。人们猜测,子集和问题很可能也不属于 P。
美国计算机科学家杰克·埃德蒙兹(Jack Edmonds)在 1964 年的一篇讨论某个矩阵问题的论文中,也提到了类似于 P 问题的概念:“当然,给定一个矩阵后,考虑所有可能的染色方案,我们一定能碰上一个符合要求的剖分,但这种方法所需要的工作量大得惊人。我们要寻找一种算法,使得随着矩阵大小的增加,工作量仅仅是呈代数式地上涨……和大多数组合问题一样,找出一个有限的算法很容易,找出一个满足上述条件的,从而能在实际中运用的算法,就不那么容易了。”接下来,埃德蒙兹模模糊糊地触碰到了一个新的概念:“给定一个矩阵,它的各列最少能被剖分成多少个独立集?我们试着找出一个好的刻画方式。至于什么叫作‘好的刻画’,我们则采用‘绝对主管原则’。一个好的刻画,应该能透露出矩阵的某些信息,使得某个主管能够在助手找到一个最小的剖分方案之后,轻易地验证出这确实是最小的剖分方案。有了一个好的刻画,并不意味着就有一个好的算法。助手很可能还是得拼死拼活,才能找到那个剖分方案。”
埃德蒙兹后面所说的,不是设计一种多项式级的算法来寻找答案,而是设计一种多项式级的算法来验证答案的正确性。对于很多问题,这件事情是很好办的。为了向人们展示出确实有可能让所有的物体都不被压坏,我们只需要给出一种满足要求的物体叠放顺序,并让计算机用 O(n) 的时间验证它的确满足要求即可。为了向人们展示出集合中的某些数加起来能得出 277,我们只需要提供一种选数的方法,并让计算机用 O(n) 的时间求和检验。
对于有些问题来说,如果答案是肯定的,我们可能并没有一种非常明显的高效方法来检验这一点。不过,很容易看出,找出一个多项式级的答案验核算法,再怎么也比找出一个多项式级的答案获取算法更容易。很多看上去非常困难的问题,都是先找到多项式级的答案验核算法,再找到多项式级的答案获取算法的。一个经典的例子就是质数判定问题。如果某个数确实是一个质数,你怎样才能在多项式级的时间里证明这一点?1975 年,沃恩·普拉特(Vaughan Pratt)在《每个质数都有一份简短的证明书》(Every Prime Has a Succinct Certificate)一文中给出了一种这样的方法,无疑推动了质数判定算法的发展。
还有些问题是如此之难,以至于目前人们不但没有找到多项式级的答案获取算法,而且还不知道是否存在多项式级的答案验核算法。比如经典的“第 K 大子集问题”(Kth largest subset problem):给定一个含有 n 个整数的集合 S,一个大整数 M,以及一个不超过 2n 的整数 K,判断出是否存在至少 K 个不同的子集,使得每个子集里的元素之和都不超过 M?如果答案是肯定的,一个很容易想到的验证方法便是,把所有满足要求的 K 个子集都列出来,并交由计算机审核。只可惜,子集的数目是指数级的,因而审核工作也将会花费指数级的时间。人们猜测,第 K 大子集问题很可能没有多项式级别的检验方法。
在复杂度理论中,一个问题有没有高效的答案验核算法,也是一个非常重要的研究课题。对于一个判定性问题,如果存在一个多项式级的算法,使得每次遇到答案应为“是”的时候,我们都能向这个算法输入一段适当的“证据”,让算法运行完毕后就能确信答案确实为“是”,我们就说这个问题是一个 NP 问题,或者说它属于集合 NP。为了解释“NP 问题”这个名字的来由,我们不得不提到 NP 问题的另一个等价定义:可以在具备随机功能的机器上用多项式级的时间解决的问题。
如果允许计算机的指令发生冲突,比如指令集里面既有 “如果遇到情况 A,则执行操作 B”,又有 “如果遇到情况 A,则执行操作 C”,我们就认为这样的计算机具备了随机的功能。这种新型的计算机就叫作“非确定型”(nondeterministic)机器。机器一旦遇到了矛盾纠结之处,就随机选择一条指令执行。你可以把机器面对的每一次随机选择都想象成是一个通向各个平行世界的岔路口,因而整台机器可以同时试遍所有的分支,自动探寻所有的可能。如果你看过尼古拉斯·凯奇(Nicolas Cage)主演的电影《预见未来》(Next),你或许会对这一幕非常熟悉。只要在任意一个分支里机器回答了“是”,那么整台机器也就算作回答了“是”。
在如此强大的机器上,很多问题都不是问题了。为了判断出能否让所有的物体都不被压坏,我们只需要让机器每次都从剩余物体中随便选一个放,看看由此产生的 n! 种放法里是否有哪种放法符合要求。为了判断出集合中是否有某些数加起来等于 277,我们只需要让机器随机决定每个数该选还是不选,最后看看有没有哪次选出来的数之和正好是 277。事实上,在非确定型计算机上可以用多项式级的时间获取到答案的问题,正是那些在确定型计算机上可以用多项式级的时间验核答案的问题,原因很简单:如果一个问题可以在非确定型计算机上获解,找到解的那个分支沿途做出的选择就成了展示答案正确性的最有力证据;反之,如果我们能在确定型计算机上验核出答案确实为“是”,我们便可以在非确定型计算机上随机产生验核所需的证据,看看在所有可能的证据当中会不会出现一条真的能通过验核的证据。“非确定型”的英文单词是 nondeterministic,它的第一个字母是 N;“多项式”的英文单词是 polynomial,它的第一个字母是 P。NP 问题便如此得名。
容易想到,所有的 P 问题一定都是 NP 问题,但反过来就不好说了。例如,子集和问题是属于 NP 的。然而,之前我们就曾经讨论过,人们不但没有找到子集和问题的多项式级解法,而且也相信子集和问题恐怕根本就没有多项式级的解法。因而,子集和问题很可能属于这么一种类型的问题:它属于集合 NP,却不属于集合 P。
1971 年,史提芬·古克(Stephen Cook)发表了计算机科学领域最重要的论文之一——《定理证明过程的复杂性》(The Complexity of Theorem-Proving Procedures)。在这篇论文里,史提芬·古克提出了一个著名的问题:P 等于 NP 吗?如果非要用一句最简单、最直观的话来描述这个问题,那就是:能高效地检验解的正确性,是否就意味着能高效地找出一个解?数十年来,无数的学者向这个问题发起了无数次进攻。根据格哈德·韦金格(Gerhard Woeginger)的统计,仅从 1996 年算起,就有 100 余人声称解决了这个问题,其中 55 人声称 P 是等于 NP 的,另外 45 人声称 P 是不等于 NP 的,还有若干人声称这个问题理论上不可能被解决。但不出所料的是,所有这些“证明”都是错误的。目前为止,既没有人真正地证明了 P = NP,也没有人真正地证明了 P ≠ NP,也没有人真正地证明了这个问题的不可解性。这个问题毫无疑问地成为了计算机科学领域最大的未解之谜。在 2000 年美国克雷数学研究所(Clay Mathematics Institute)公布的千禧年七大数学难题(Millennium Prize Problems)中,P 和 NP 问题排在了第一位。第一个解决该问题的人将会获得一百万美元的奖金。
让我们来看一下,科学家们都是怎么看 P 和 NP 问题的吧。英国数学家、生命游戏(Game of Life)的发明者约翰·康威(John Conway)认为,P 是不等于 NP 的,并且到了 21 世纪 30 年代就会有人证明这一点。他说道:“我觉得这本来不应该是什么难题,只是这个理论来得太迟,我们还没有弄出任何解决问题的工具。”美国计算机科学家、1985 年图灵奖获得者理查德·卡普(Richard Karp)也认为,P 是不等于 NP 的。他说:“我认为传统的证明方法是远远不够的,解决这个问题需要一种绝对新奇的手段。直觉告诉我,这个问题最终会由一位不被传统思想束缚的年轻科学家解决掉。”美国计算机科学家、《自动机理论、语言和计算导论》(Introduction to Automata Theory, Languages and Computation)的作者杰夫瑞·厄尔曼(Jeffrey Ullman)同样相信 P 不等于 NP。他说:“我认为这个问题和那些困扰人类上百年的数学难题有得一拼,比如四色定理(four color theorem)。所以我猜测,解决这个问题至少还要 100 年。我敢肯定,解决问题所需的工具至今仍未出现,甚至连这种工具的名字都还没有出现。但别忘了,那些最伟大的数学难题刚被提出来的 30 年里,所面对的也是这样的情况。”
你或许会注意到,大家似乎都倾向于认为 P ≠ NP 。事实上,根据威廉·加萨奇(William Gasarch)的调查,超过八成的学者都认为 P ≠ NP。这至少有两个主要的原因。首先,证明 P = NP 看上去比证明 P ≠ NP 更容易,但即使这样,目前仍然没有任何迹象表明 P = NP。为了证明 P = NP,我们只需要构造一种可以适用于一切 NP 问题的超级万能的多项式级求解算法。在那篇划时代的论文里,史提芬·古克证明了一个颇有些出人意料的结论,让 P = NP 的构造性证明看起来更加唾手可得。给你一堆正整数,问能否把它们分成总和相等的两堆,这个问题叫作“分区问题”(partition problem)。容易看出,分区问题可以转化为子集和问题的一个特例,你只需要把子集和问题中的目标设定成所有数之和的一半即可。这说明,子集和问题是一个比分区问题更一般的“大问题”,它可以用来解决包括分区问题在内的很多“小问题”。史提芬·古克则证明了,在 NP 问题的集合里,存在至少一个最“大”的问题,它的表达能力如此之强,以至于一切 NP 问题都可以在多项式的时间里变成这个问题的一种特例。很容易想到,如果这样的“终极 NP 问题”有了多项式级的求解算法,所有的 NP 问题都将拥有多项式级的求解算法。这样的问题就叫作“NP 完全问题”(NP-complete problem)。在论文中,史提芬·古克构造出了一个具体的 NP 完全问题,它涉及到了很多计算机底层的逻辑运算,能蕴含所有的 NP 问题其实也不是非常奇怪的事。
后来,人们还找到了很多其他的 NP 完全问题。1972 年,理查德·卡普发表了《组合问题中的可归约性》(Reducibility among Combinatorial Problems)一文。这是复杂度理论当中又一篇里程碑式的论文,“P 问题”、“NP 问题”、“NP 完全问题”等术语就在这里诞生。在这篇论文里,理查德·卡普列出了 21 个 NP 完全问题,其中不乏一些看起来很“正常”、很“自然”的问题,刚才提到的子集和问题就是其中之一。1979 年,迈克尔·加里(Michael Garey)和戴维·约翰逊(David Johnson)合作出版了第一本与 NP 完全问题理论相关的教材——《计算机和难解性:NP 完全性理论导引》(Computers and Intractability: A Guide to the Theory of NP-Completeness)。该书的附录中列出了超过 300 个 NP 完全问题,这一共用去了 100 页的篇幅,几乎占了整本书的三分之一。如果这些 NP 完全问题当中的任何一个问题拥有了多项式级的求解算法,所有的 NP 问题都将自动地获得多项式级的求解算法,P 也就等于 NP 了。然而,这么多年过去了,没有任何人找到任何一个 NP 完全问题的任何一种多项式解法。这让人们不得不转而相信,P 是不等于 NP 的。
人们相信 P ≠ NP 的另一个原因是,这个假设经受住了实践的考验。工业与生活中的诸多方面都依赖于 P ≠ NP 的假设。如果哪一天科学家们证明了 P = NP,寻找一个解和验证一个解变得同样容易,这个世界将会大不一样。1995 年,鲁塞尔·因帕利亚佐(Russell Impagliazzo)对此做了一番生动描述。
首先,各种各样的 NP 问题,尤其是那些最为困难的 NP 完全问题,都将全部获得多项式级的解法。工业上、管理上的几乎所有最优化问题都立即有了高效的求解方案。事实上,我们甚至不需要编程告诉计算机应该怎样求解问题,我们只需要编程告诉计算机我们想要什么样的解,编译器将会自动为我们做好一个高效的求解系统。其次,很多人工智能问题也迎刃而解了。比方说,为了让计算机具备中文处理能力,我们可以准备一个训练集,里面包含一大批句子样本,每个句子都带有“符合语法”、“不符合语法”这两种标记之一。接下来,我们要求计算机构造一个代码长度最短的程序,使得将这些语句输入这个程序后,程序能正确得出它们是否符合语法。显然,这个最优化问题本身是一个 NP 问题(这里有个前提,即这样的程序是存在的,并且是多项式级别的),因此计算机可以在多项式时间内找到这个最简程序。根据奥卡姆剃刀原理(Occam’s razor),我们有理由相信,这个程序背后的算法也就是人类头脑中正在使用的算法,因此它能够适用于所给材料之外的其他语句,并具有自我学习的功能。数学家的很多工作也可以完全交给计算机来处理。寻找一个反例和验证一个反例变得同样简单,各种错误的猜想都将很快被推翻。事实上,寻找一个数学证明和验证一个证明的正确性也变得同样简单,因此各种正确的命题也能够很快找到一个最简的证明。
最后,不要高兴得太早——P = NP 的世界也将会是一个极不安全的世界。电子签名技术不再有效,因为伪造一段合法的签名变得和验证签名是否合法一样轻松。RSA 算法也不再有效,因为寻找一个质因数变得和判断整除性一样简单。事实上,发明任何新的密码算法都是徒劳——计算机可以根据一大批明文密文样本推算出生成密文的算法(只要这个算法本身是多项式的)。更进一步,在网络上,你再也没法把人和人区别开来,甚至没法把人和计算机区别开来。计算机不仅能轻易通过图灵测试(Turing test),还能精确地模仿某一个特定的人。如果你能把某个人的网络聊天记录全部搜集起来,把这个人和网友们的对话全部递交给计算机,计算机将会很快学会如何模仿这个人。网络的身份鉴定必须要借助物理手段。即使是在科幻故事中,这样的设定也相当疯狂,可见 P = NP 有多不可能了。
虽然种种证据表明 P ≠ NP,但我们仍然无法排除 P = NP 的可能性。其实,如果 P 真的等于 NP,但时间复杂度的次数非常大非常大非常大,密码学的根基仍然不太可能动摇,我们的世界仍然不太可能大变。被誉为“算法分析之父”的计算机科学大师高德纳(Donald Knuth)还提出了这样一种可能:未来有人利用反证法证明了 P = NP,于是我们知道了所有 NP 问题都有多项式级的算法,但算法的时间复杂度究竟是多少,我们仍然一无所知!
对于很多人来说,找不到任何一个 NP 完全问题的多项式级算法,同样不应成为质疑 P = NP 的理由。荻原光德(Mitsunori Ogihara)认为,最终人们或许会成功地证明 P = NP,但这绝不是一两个人死死纠缠某一个 NP 完全问题就能办到的。对此,他做了更为细致的想象。
XX 世纪后期,一份非常简略的、从未发表过的草稿,无意中开辟了解决 P 和 NP 问题的道路。这份草稿出自 20 世纪的一位数学天才 FOO 之手,当时他正在尝试着建立某种代数结构的新理论。显然,FOO 很快放弃了这个想法,并且今后从未重新拾起这个课题。这份草稿一直卡在 FOO 的卧室地板的缝隙里,在后来的一次旧房翻新工程中才被工人们发现。由于草稿太过简略,因而当时并未引起太多关注。然而,几十年后,一群数学家发现,如果草稿上面的某个假设的某个变形成立,将会推出很多有意思的东西。虽然这不是 FOO 本来要做的假设,但它还是被人们称作“FOO 假设”,以纪念这位数学天才。
大约 100 年后,一群计算机科学家发现,如果 FOO 假设成立,那么某个特定的代数问题 Q 将会成为一个 NP 完全问题。几年后,计算机科学家们再次发现,如果(届时已经非常有名的)BAR 猜想成立,那么 Q 将会拥有多项式级的算法。把两者结合起来,于是得到:如果 FOO 和 BAR 都成立,那么 P = NP。
接下来的两个世纪里,这两个猜想都有了相当充分的研究。人们不断地得出各式各样的部分结果,剩余的特例则被转化为新的形式,直至每个猜想都被归为一句非常简明、非常具体的命题。最终,两组人马相继宣布,这两个命题都是正确的。第一组人马在 FOO 的诞辰前三周宣布,他们终于攻克了 BAR 猜想的最后一环。三个月后,第二组人马宣布,FOO 猜想正式得以解决。
未来究竟会发生什么?让我们拭目以待。
再过16年,娃都要谈恋爱喽
❤️ 看 黃 魸【 6kkm.xyz 】偸 啪 【 6kkm.xyz 】佬 呞 机~你 慬 的 ❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖❤️➖
鸽子你更新了!
最后结尾莫名想起了何夕的《伤心者》~~
爷青回
问题十分场景化,很有意思
每个人的额外收入。 https://rawl.startupers.se/gotodate/go
没想到2022年仍然有人在这个论坛打广告,不知道是真人还是自动程序
赚钱是很容易的,如果你使用金融机器人。 https://rawl.startupers.se/gotodate/go
Купить фляжку в подарок в розницу и подарки на открытие бизнеса в Махачкале.
Новогодние деревянные подарки оптом и подарки в коробке в Тюмени.
Source:
https://suveniri-podarki-1.ru
对于每个追求财务独立的人来说,这是最好的方法。 https://rawl.startupers.se/gotodate/go
找出最简单的赚钱方法。 https://rawl.startupers.se/gotodate/go
又见博主。我记得好多年前读过一篇统计红楼梦的博文,找不到了,好像在找出来读一下,望博主拨云见日一下下
失踪人口回归了
滋瓷
看看自动机器人,它为你工作24/7。 https://rawl.seamonkey.es/gotodate/go
只需点击一下就可以让你的钱增长得非常快。 https://rawl.seamonkey.es/gotodate/go
没有必要担心未来,如果你使用这个金融机器人。 https://rawl.seamonkey.es/gotodate/go
财务独立是每个人都需要的。 https://rawl.seamonkey.es/gotodate/go
你的每一美元都可以在你吃过这个机器人后变成100美元。 https://rawl.seamonkey.es/gotodate/go
没有必要再找工作了。 在线工作。 https://rawl.seamonkey.es/gotodate/go
即使是孩子也知道如何赚钱。 这个机器人就是你所需要的! https://rawl.seamonkey.es/gotodate/go
只需点击一下就可以让你的钱增长得非常快。 https://rawl.seamonkey.es/gotodate/go
没有必要担心未来,如果你使用这个金融机器人。 https://rawl.seamonkey.es/gotodate/go
注意! 金融机器人可能会给你带来数百万! https://rawl.seamonkey.es/gotodate/go
赚美元呆在家里,推出了这个机器人。 https://rawl.seamonkey.es/gotodate/go
如果你使用这个机器人,在线工作真的很有效。 https://rawl.seamonkey.es/gotodate/go
没有必要担心未来,如果你使用这个金融机器人。 https://rawl.seamonkey.es/gotodate/go
小额投资可以很快带来成吨的美元。 https://rawl.seamonkey.es/gotodate/go
即使是一个孩子知道如何使$100今天。 https://rawl.seamonkey.es/gotodate/go
如果你使用这个机器人,在线工作真的很有效。 https://rawl.seamonkey.es/gotodate/go
大多数成功的人已经使用机器人。 你呢? https://rawl.seamonkey.es/gotodate/go
如果你使用这个机器人,可以保证数千美元。 https://rawl.seamonkey.es/gotodate/go
注意! 在这里,您可以在线赚钱! https://rawl.seamonkey.es/gotodate/go
这个机器人可以给你带来24/7的钱。 https://rawl.seamonkey.es/gotodate/go
时过多年,居然更新了。支持!
金融机器人是你赚钱的第一专家. https://rawl.seamonkey.es/gotodate/go
如果你使用这个金融机器人,每天赚1000美元很容易。 https://rawl.seamonkey.es/gotodate/go
找到最好的在线投资工具。 了解更多! https://rawl.seamonkey.es/gotodate/go
在线收入是财务独立的最简单方法。 https://rawl.seamonkey.es/gotodate/go
在线机器人将为您带来财富和满足感。 https://rawl.seamonkey.es/gotodate/go
#网络金融专家! 看看新的机器人。 https://rawl.seamonkey.es/gotodate/go
使用金融机器人开始您的在线工作。 https://rawl.seamonkey.es/gotodate/go
只需点击一下即可将您的美元变成$1000。 https://rawl.seamonkey.es/gotodate/go
尝试在互联网上最好的金融机器人。 https://rawl.seamonkey.es/gotodate/go
在线收入是财务独立的最简单方法。 https://rawl.seamonkey.es/gotodate/go
让你钱包变厚的最快方法就在这里。 https://rawl.seamonkey.es/gotodate/go
没有必要整夜保持清醒来赚钱。 启动机器人。 https://rawl.seamonkey.es/gotodate/go
找出财务独立的最快方法。 https://rawl.seamonkey.es/gotodate/go
即使是一个孩子也知道如何在这个机器人的帮助下赚100美元。 https://rawl.seamonkey.es/gotodate/go
需要现金吗? 启动这个机器人,看看它可以。 https://rawl.seamonkey.es/gotodate/go
看着你的钱增长,而你与机器人投资。 https://rawl.seamonkey.es/gotodate/go
学习如何每天制作数百个背。 https://rawl.seamonkey.es/gotodate/go
找到最好的在线投资工具。 了解更多! https://rawl.seamonkey.es/gotodate/go
如果你使用这个机器人,可以保证数千美元。 https://rawl.seamonkey.es/gotodate/go
没有钱? 在这里在线赚取它们很容易。 https://rawl.seamonkey.es/gotodate/go
#网络金融专家! 看看新的机器人。 https://rawl.seamonkey.es/gotodate/go
尝试自动机器人整天保持收入。 https://rawl.seamonkey.es/gotodate/go
没有钱? 在这里在线赚取它们很容易。 https://rawl.seamonkey.es/gotodate/go
加入在这里赚钱的成功人士的社会。 https://rawl.seamonkey.es/gotodate/go
金融机器人是你的成功公式被发现。 了解更多信息。 https://rawl.seamonkey.es/gotodate/go
没有钱? 在线赚取。 https://rawl.seamonkey.es/gotodate/go
如果你使用这个机器人,可以保证数千美元。 https://rawl.seamonkey.es/gotodate/go
每个人都可以赚多少,因为他想起诉这个机器人。 https://rawl.seamonkey.es/gotodate/go
当你启动机器人时,不需要再工作了! https://rawl.seamonkey.es/gotodate/go
看看自动机器人,它为你工作24/7。 https://rawl.seamonkey.es/gotodate/go
即使是孩子也知道如何赚钱。 这个机器人就是你所需要的! https://rawl.seamonkey.es/gotodate/go
金融机器人是你赚钱的第一专家. https://rawl.seamonkey.es/gotodate/go
小额投资可以很快带来成吨的美元。 https://rawl.startupers.se/gotodate/go
如果你使用金融机器人,你的钱会持续增长24/7。 https://rawl.startupers.se/gotodate/go
金融机器人是您未来的财富和独立性。 https://rawl.startupers.se/gotodate/go
启动机器人,让它带给你的钱。 https://rawl.startupers.se/gotodate/go
这个机器人将帮助你每天赚几百美元。 https://rawl.startupers.se/gotodate/go
只需点击一下机器人就可以为您带来数千美元。 https://rawl.startupers.se/gotodate/go
让你的电脑成为你赚钱的工具. https://rawl.startupers.se/gotodate/go
你的每一美元都可以在你吃过这个机器人后变成100美元。 https://rawl.startupers.se/gotodate/go
只需点击一下就可以让你的钱增长得非常快。 https://rawl.startupers.se/gotodate/go
使用金融机器人开始您的在线工作。 https://rawl.startupers.se/gotodate/go
如果你使用这个金融机器人,每天赚1000美元很容易。 https://rawl.startupers.se/gotodate/go
额外的收入可用于使用此机器人的每个人。 https://rawl.startupers.se/gotodate/go
没有钱? 在线赚取。 https://rawl.startupers.se/gotodate/go
在线金融机器人是你成功的关键. https://rawl.elletvweb.it/gotodate/go
没有必要担心未来,如果你使用这个金融机器人。 https://rawl.elletvweb.it/gotodate/go
金融机器人是一个伟大的方式来管理和增加你的收入。 https://rawl.elletvweb.it/gotodate/go
①期待新作
②评论区的刷屏机器人是什么玩意儿?
这个机器人可以给你带来24/7的钱。 https://rawl.elletvweb.it/gotodate/go
即使是孩子也知道如何赚钱。 你呢? https://rawl.elletvweb.it/gotodate/go
#网络金融专家! 看看新的机器人。 https://rawl.elletvweb.it/gotodate/go
10年后博主还在更新哈哈
现在每个人都可以赚多少钱。 https://rawl.elletvweb.it/gotodate/go
在线工作可以为您带来丰厚的利润。 https://rawl.elletvweb.it/gotodate/go
需要钱吗? 金融机器人是你的解决方案。 https://rawl.elletvweb.it/gotodate/go
尝试自动机器人整天保持收入。 https://rawl.elletvweb.it/gotodate/go
该启用垃圾评论过滤器了
让自己丰富的未来使用这个金融机器人。 https://rawl.frostyelk.se/gotodate/go
使用这个机器人在互联网上赚钱。 它确实有效! https://rawl.frostyelk.se/gotodate/go
这个机器人可以给你带来24/7的钱。 https://rawl.frostyelk.se/gotodate/go
财务独立是每个人都需要的。 https://rawl.frostyelk.se/gotodate/go
财务独立是这个机器人的保证。 https://rawl.frostyelk.se/gotodate/go
看开头,还以为是译文
需要钱吗? 轻松拿到这里? https://rawl.frostyelk.se/gotodate/go
金融机器人是网络中最有效的金融工具! https://rawl.frostyelk.se/gotodate/go
让你的电脑成为你赚钱的工具. https://rawl.frostyelk.se/gotodate/go
启动机器人,让它带给你的钱。 https://rawl.frostyelk.se/gotodate/go
相信金融机器人变得富有。 https://rawl.frostyelk.se/gotodate/go
每个需要钱的人都应该试试这个机器人。 https://rawl.frostyelk.se/gotodate/go
在线收入是你成功的关键。 https://rawl.frostyelk.se/gotodate/go
使用这个机器人是让你致富的最好方法。 https://rawl.frostyelk.se/gotodate/go
只需点击一下即可将您的美元变成$1000。 https://rawl.frostyelk.se/gotodate/go
需要现金吗? 启动这个机器人,看看它可以。 https://rawl.frostyelk.se/gotodate/go
这个机器人可以给你带来24/7的钱。 https://rawl.frostyelk.se/gotodate/go
金融机器人是你赚钱的第一专家. https://rawl.frostyelk.se/gotodate/go
使用金融机器人开始您的在线工作。 https://rawl.frostyelk.se/gotodate/go
期待收入? 上网吧。 https://rawl.frostyelk.se/gotodate/go
财务独立是每个人都需要的。 https://rawl.frostyelk.se/gotodate/go
需要现金吗? 启动这个机器人,看看它可以。 https://rawl.frostyelk.se/gotodate/go
加入在这里赚钱的成功人士的社会。 https://rawl.frostyelk.se/gotodate/go
还是不是百万富翁? 金融机器人会让你成为他! https://rawl.frostyelk.se/gotodate/go
寻找一个简单的赚钱方法? 看看金融机器人。 https://rawl.frostyelk.se/gotodate/go
相信金融机器人变得富有。 https://rawl.frostyelk.se/gotodate/go
你的每一美元都可以在你吃过这个机器人后变成100美元。 https://rawl.frostyelk.se/gotodate/go
前段时间拜读了您的那篇文章,受益匪浅。
赚取额外的钱没有努力和技能。 https://rawl.pumpati.de/rawl
现在每个人都可以赚多少钱。 https://rawl.pumpati.de/rawl
在线机器人将为您带来财富和满足感。 https://rawl.pumpati.de/rawl
期待收入? 上网吧。 https://rawl.pumpati.de/rawl
哇塞! 这个机器人是在线职业生涯的一个很好的开始。 https://rawl.pumpati.de/rawl
启动金融机器人,做你的生意。 https://rawl.pumpati.de/rawl
使用此程序使您的笔记本电脑成为金融工具。 https://rawl.pumpati.de/rawl
网上赚钱,这个寒冷的冬天呆在家里。 https://rawl.pumpati.de/rawl
金融机器人是一个伟大的方式来管理和增加你的收入。 https://rawl.pumpati.de/rawl
即使是孩子也知道如何赚钱。 你呢? https://rawl.qbe-medienhaus.de/rawl
如果你使用机器人,在互联网上赚钱很容易。 https://rawl.qbe-medienhaus.de/rawl
我们知道如何让我们的未来变得富有,你呢? https://rawl.qbe-medienhaus.de/rawl
一美元算不了什么,但它可以在这里成长为$100。 https://rawl.qbe-medienhaus.de/rawl
金融机器人保证每个人的稳定和收入。 https://rawl.qbe-medienhaus.de/rawl
寻找一个简单的赚钱方法? 看看金融机器人。 https://rawl.qbe-medienhaus.de/rawl
自动机器人是财务独立的最佳开端。 https://rawl.qbe-medienhaus.de/rawl
Teen Girls Pussy Pics. Hot galleries
http://modbus.categories.hoterika.com/?emilia
fee porn tube video free women flashing porn vids estonia gay porn baby girl vagina porn skateboarding porn
赚钱,而不是战争! 金融机器人是你所需要的。 https://rawl.qbe-medienhaus.de/rawl
赚取额外的钱没有努力和技能。 https://rawl.qbe-medienhaus.de/rawl
使用此程序使您的笔记本电脑成为金融工具。 https://rawl.qbe-medienhaus.de/rawl
自动机器人是财务独立的最佳开端。 https://rawl.qbe-medienhaus.de/rawl
推出最好的投资工具,今天开始赚钱。 https://rawl.qbe-medienhaus.de/rawl
需要钱吗? 轻松拿到这里? https://rawl.qbe-medienhaus.de/rawl
赚美元呆在家里,推出了这个机器人。 https://rawl.qbe-medienhaus.de/rawl
这是启动机器人以获得更多资金的最佳时机。 https://rawl.qbe-medienhaus.de/rawl
找到最好的在线投资工具。 了解更多! https://rawl.qbe-medienhaus.de/rawl
尝试在互联网上最好的金融机器人。 https://rawl.baobab-erding.de/rawl
在线收入是财务独立的最简单方法。 https://rawl.gizmo-inc.fr/rawl
每周在这里在线工作数千人。 https://rawl.gizmo-inc.fr/rawl
在线工作可以为您带来丰厚的利润。 https://rawl.gizmo-inc.fr/rawl
我们知道如何提高你们的财务稳定性。 https://rawl.gizmo-inc.fr/rawl
在几分钟内从1美元赚1000美元。 现在启动金融机器人。 https://rawl.gizmo-inc.fr/rawl
我们知道如何致富,你呢? https://rawl.chronicleshardcore.de/rawl
使用这个机器人在互联网上赚钱。 它确实有效! https://rawl.chronicleshardcore.de/rawl
即使是一个孩子也知道如何在这个机器人的帮助下赚100美元。 https://rawl.chronicleshardcore.de/rawl
相信你的美元给机器人,看看它是如何增长到$100。 https://rawl.danceit.es/rawl
你的每一美元都可以在你吃过这个机器人后变成100美元。 https://rawl.danceit.es/rawl
没有必要再找工作了。 在线工作。 https://rawl.danceit.es/rawl
钱,钱! 用金融机器人赚更多的钱! https://rawl.danceit.es/rawl
如果你使用这个机器人,你的电脑可以给你带来额外的收入. https://rawl.danceit.es/rawl
开始每周只用这个机器人赚几千美元。 https://rawl.danceit.es/rawl
在线收入是让你梦想成真的最简单方法。 https://rawl.danceit.es/rawl
卧槽诈尸!
上次看的时候我还没孩子
现在也没有
需要钱吗? 轻松拿到这里! 只要按这个启动机器人。 https://rawl.echinat.de/rawl
财务独立是这个机器人的保证。 https://rawl.echinat.de/rawl
即使你睡觉,金融机器人也为你工作。 https://rawl.echinat.de/rawl
退休人员最好的在线工作。 让你的晚年富有。 https://rawl.echinat.de/rawl
寻找额外的钱? 尝试最好的金融工具。 https://rawl.echinat.de/rawl
在线机器人将为您带来财富和满足感。 https://rawl.echinat.de/rawl
让你的钱整天为你工作。 https://rawl.echinat.de/rawl
没有投资的巨额收入是可用的。 https://rawl.echinat.de/rawl
机器人从不睡觉。 它为你赚钱24/7。 https://rawl.echinat.de/rawl
钱,钱! 用金融机器人赚更多的钱! https://rawl.echinat.de/rawl
额外的收入可用于使用此机器人的每个人。 https://rawl.echinat.de/rawl
太感慨了,我从小学看到初中然后断更了
这个机器人将帮助你每天赚几百美元。 https://rawl.mir-und-mich.de/
赚美元呆在家里,推出了这个机器人。 https://Calk.mir-und-mich.de/
这机器人咋还在刷屏
Hot galleries, daily updated collections
http://brown-itchy.spots-on.skin.instakink.com/?julie
donkey party amateur porn shits out porn porn upload yourtube celebs and porn blonde adult porn stars
好文,好机器人。
Slot Gacor menyediakan situs slot gacor 2023 dibekali
provider slot online terpercaya dan terbaru. Daftar & mainkan games
judi online terbaik disini. Situs slot resmi tergacor adalah sebuah situs permainan slot atau situs slot gacor terpercaya yang menampilkan video game gulungan berisi simbol-simbol tertentu.
Ada banyak slot gacor terbaru dari provider slot gacor 2023 berkelas
Internasional, seperti provider situs slot gacor hari ini Pragmatic Play, situs slot online terpercaya Spadegaming,
situs slot terpercaya 2023 Microgaming, situs slot terbaru 2023
Joker Gaming, situs slot terbaik CQ9, situs slot tanpa potongan PGSoft, dan masih banyak lagi provider situs slot paling gacor atau
situs slots gacor yang ada.
Semua provider tersebut berlomba–lomba membuat slot paling gacor untuk para pemainnya membuat kamu bisa dengan mudah
bermain slot yg gacor hari ini dengan mengikuti info slot gacor hari ini.
Makin meningkatnya permintaan slot yang gacor hari ini membuat banyak situs slot luar negeri muncul termasuk di Indonesia.
Situs-situs tersebut menawarkan seperti situs slot Pragmatic atau agen gacor lainnya.
Walaupun demikian, terdapat beberapa situs slot gacor
malam ini palsu yang menawarkan daftar slot gacor gampang menang tanpa
lisensi resmi atau slot yang lagi gacor abal-abal. Hal tersebut membuat kamu harus lebih selektif dalam
memilih situs slot terpercaya 2023 yang benar-benar memberikan slot yg lagi gacor terbaik.
Slot Gacor adalah situs slot online terbaik dan terpercaya gampang menang 2023
yang memberikan slot online gacor resmi hingga slot gacor maxwin. Memiliki fasilitas situs slot bonus
New Member 100 sehingga kamu tidak perlu ragu untuk
membuat akun slot gacor di situs ini. Ada juga bocoran slot
gacor hari ini yang bisa kamu temukan di website slot gacor Slot Gacor yang bisa menjadi pedoman dalam memilih judi
slot gacor. Terdapat pula jenis permainan lainnya di situs slot tergacor,
mulai dari situs slot hoki Sportsbook, situs slot gampang menang Casino Live, situs slot88 Poker Live, situs dewa slot 88 Tembak Ikan online dan masih banyak
lagi BO slot gacor julukan lainnya yang disematkan pada situs Slot Gacor ini.
Nikmati keseruan bermain beragam jenis judi online hanya
di situs yang tepat dan terpercaya seperti halnya situs Slot88.
https://bphtb.bapenda.padang.go.id/slot-gacor/
Hmm it appears like your site ate my first comment (it was extremely long) so I guess I’ll
just sum it up what I had written and say, I’m
thoroughly enjoying your blog. I as well am an aspiring blog blogger but I’m still new to the
whole thing. Do you have any helpful hints for rookie blog writers?
I’d really appreciate it.
I think that everything composed made a bunch of sense.
However, what about this? what if you were to write a killer headline?
I ain’t saying your information isn’t solid, but what if you added a headline that makes people
desire more? I mean 16 年后重谈 P 和 NP | Matrix67: The
Aha Moments is kinda vanilla. You might glance at Yahoo’s home page
and watch how they write post headlines to get people to open the
links. You might try adding a video or a related picture or two to grab
people excited about what you’ve got to say.
Just my opinion, it could bring your blog a little
bit more interesting.
My blog post rtp Pay4D live
Paragraph writing is also a fun, if you be familiar with then you can write if not it is difficult
to write.
Also visit my homepage: daftar situs pg soft gacor
Mostbet idmana mərc edə və müxtəlif virtual oyunlar
oynaya biləcəyiniz beynəlxalq populyar platformadır.
BC-nin Curacao adasından lisenziyası var.
Onlayn bukmeker kontoru beynəlxalq bazarda
fəaliyyətə 2009-cu ildə başlayıb.
mostbet.az müştəriləri dünyanın hər yerindəndir,
onlar burada 100-ə yaxın ölkədən qeydiyyatdan keçirlər.
Rəsmi internet saytı 25 dilə tərcümə olunub.
Hər gün minlərlə yeni insan bu peşəkar bahisçi ilə qeydiyyatdan keçir və peşəkar oyunçular və bahisçilər
çoxlu sayda müsbət şərhlər və reytinqlər buraxırlar.
Müştərilər Mostbet-i əlçatan interfeysə, əla funksionallığa, əsas
bölmələr arasında cəld keçid etməyə imkan verən rahat
menyuya görə tərifləyirlər. Xoş gözə çarpmayan dizayn bukmeker kontorunda fəaliyyətinizi həqiqətən maraqlı edəcək.
Dünya valyutalarının geniş çeşidi də mövcuddur – azn, rubl, dollar, avro,
tenge (cəmi 19 seçim).
Mostbet-də qeydiyyatdan keçin və keyfiyyətli oyuna
başlayın və bu gün də işləyin. CC ilə tamamilə fərqli səviyyəyə aparın!
Mostbet geniş imkanlar təklif edir. Bu BC digər rəqiblərin fonunda əhəmiyyətli dərəcədə qalib gəlir.
Sizə adekvat idman seçimi (ümumilikdə 20 fən), kifayət qədər aşağı marja, çoxlu mərc seçimləri və çoxlu faydalı məlumatlar təqdim olunacaq.
Yüksək əmsallar və həmişə sürətli və etibarlı ödənişlər var
324
What’s up, its nice article about media print, we all be
aware of media is a wonderful source of data.
Do you mind if I quote a couple of your posts as long as I provide credit and
sources back to your weblog? My website is in the very same
niche as yours and my visitors would certainly benefit from a lot of
the information you present here. Please let me know
if this alright with you. Many thanks!
After exploring a number of the articles on your blog, I truly like your technique of writing a
blog. I saved it to my bookmark website list and will be checking back soon. Please check
out my web site as well and let me know what you think.
Feel free to visit my web page; slot88
I don’t know whether it’s just me or if perhaps everybody else encountering issues with your website.
It appears as if some of the written text within your posts are running off
the screen. Can someone else please provide feedback
and let me know if this is happening to them too? This might
be a issue with my browser because I’ve had
this happen previously. Thanks
https://nice-words.ir/راهنمای-پارتیشن-بندی-تقسیم-کردن-ساختا/
Thanks a bunch for sharing this with all folks you actually recognize what you’re
speaking about! Bookmarked. Kindly additionally consult with my
web site =). We may have a hyperlink alternate arrangement among us
بهترین جراح پلک مشهد
خبرهای تازه امروز و اخبار علمی پزشکی و اخبار ورزشی
پو و خبرهای تازه ولایت سرپل و خبرهای قوه قضاییه و خبرهای تازه علمی
https://bmw48025.losblogos.com/17284046/?????-????-???-?????-??????????
ردیاب خودرو مجیک بوف مدل gvt-110 و ردیاب خودرو جی پی اس ترکر مدل 303 g
و ردیاب خودرو جیپیران و ردیاب خودرو ژاپنی و ردیاب خودرو تیبا و ردیاب خودرو بهترین
Do you mind if I quote a couple of your posts as
long as I provide credit and sources back to your website?
My blog site is in the very same area of interest as yours and my users would definitely benefit from a lot of the information you present here.
Please let me know if this alright with you. Cheers!
It’s the best time to make some plans for the longer term
and it’s time to be happy. I’ve learn this
submit and if I may I want to recommend you some interesting issues
or tips. Perhaps you could write next articles regarding this article.
I want to learn even more issues approximately it!
https://sister.unpas.ac.id/slot-gacor/
Do you mind iif I quote a couple of your articls as long as I provide creditt and sources back to your webpage?
My website is in the exact same area of ibterest as yours and my users
would definitely benefit from a lot of the information you
present here. Please let me know if this alright
with you. Regards!
my blog … RAJAWIN
Pretty nice post. I just stumbled upon your blog and wished to
say that I’ve really enjoyed surfing around your blog posts.
After all I’ll be subscribing to your rss feed and I hope you write again very soon!
You really make it appear so easy with your presentation but I find this matter to be really one thing which I believe I might by no means understand.
It seems too complicated and very vast for
me. I am taking a look forward for your next post, I’ll attempt to get
the grasp of it!
Woah! I’m really loving the template/theme of this site.
It’s simple, yet effective. A lot of times it’s
challenging to get that “perfect balance” between superb usability
and appearance. I must say you’ve done a excellent job with
this. Additionally, the blog loads very fast for me on Opera.
Exceptional Blog!
Thanks in favor of sharing such a good thought, post is fastidious,
thats why i have read it entirely
Wow, marvelous blog layout! How long have you been blogging for?
you made blogging look easy. The overall look of your
website is wonderful, as well as the content!
This post will assist the internet users for creating new website or even a blog from
start to end.
I like what you guys are up too. This sort of clever work and coverage!
Keep up the amazing works guys I’ve you guys to my personal blogroll.
https://nationaliran.ir/انواع-موتور-پمپ-آب-کشاورزی-دیزلی/
Hey just wanted to give you a quick heads up. The text in your article seem to be running off the screen in Firefox.
I’m not sure if this is a formatting issue or something to do with internet browser compatibility but I figured I’d post to let you know.
The design look great though! Hope you get the problem resolved
soon. Kudos
Thank you a lot for sharing this with all of us you actually realize what
you are talking about! Bookmarked. Kindly also seek advice from my
website =). We will have a link trade arrangement among
us
With havin so much content and articles do you ever run into any issues of plagorism or copyright infringement?
My website has a lot of completely unique content I’ve either created myself or outsourced
but it appears a lot of it is popping it up all over the internet without my authorization. Do
you know any solutions to help reduce content from being ripped off?
I’d genuinely appreciate it.
Good article! We will be linking to this particularly great post on our website.
Keep up the great writing.
Wow, marvelous weblog structure! How lengthy have you been running a blog
for? you make running a blog glance easy. The whole glance of your web site is great, let alone the content material!
Awesome article.
After checking out a few of the blog posts on your website, I
truly appreciate your technique of blogging. I book marked it to my bookmark site
list and will be checking back soon. Please visit my web site as well and
let me know your opinion.
Nicely expressed certainly. !
Feel free to surf to my homepage: Dave Bolno (https://www.tumblr.com/zepho-blog/13167536246/drakes-take-care-thank-you-note)
hello there and thank you for your info – I have definitely picked up something new from right here.
I did however expertise a few technical points using this
site, since I experienced to reload the web site many times previous to
I could get it to load properly. I had been wondering if your hosting is OK?
Not that I am complaining, but slow loading instances times will very
frequently affect your placement in google and can damage your quality score if advertising
and marketing with Adwords. Anyway I’m adding this RSS to my
e-mail and can look out for much more of your respective fascinating content.
Make sure you update this again very soon.
You actually make it seem so easy with your presentation but I find this topic to be actually something
which I think I would never understand. It seems too complex and very broad for me.
I’m looking forward for your next post, I’ll try to get the hang of it!
Why users still use to read news papers when in this technological world the whole thing
is presented on net?
I like the valuable information you supply for your articles.
I will bookmark your blog and test once more here frequently.
I am rather sure I’ll be told plenty of new stuff proper here!
Best of luck for the next!
After exploring a handful of the articles on your blog, I truly like your way
of blogging. I book-marked it to my bookmark website list and will be checking back soon. Take a look at my website as
well and tell me your opinion.
I think this is among the most important information for me.
And i am glad reading your article. But should remark
on some general things, The website style is great, the articles is really great : D.
Good job, cheers
Great work! That is the kind of info that should be
shared across the web. Shame on the seek engines for no longer positioning this post higher!
Come on over and talk over with my web site . Thank you =)
When some one searches for his essential thing, so he/she wants
to be available that in detail, so that thing is maintained over here.
I’ll immediately snatch your rss as I can’t to find your email subscription link or newsletter service.
Do you’ve any? Kindly permit me understand in order that I may just subscribe.
Thanks.
I’m curious to find out what blog system you have been using?
I’m experiencing some small security issues with my latest website and I would like to find something more secure.
Do you have any suggestions?
It’s the best time to make some plans for the future and it’s time to be happy.
I have read this post and if I could I wish to suggest you few interesting things or
tips. Maybe you could write next articles referring to this article.
I desire to read even more things about it!
Appreciate it. Loads of material!
my website Dave T Bolno (https://variety.com/list_item/david-bolno/)
This is my first time go to see at here and i am actually impressed to read all at alone place.
I am really loving the theme/design of your weblog. Do you ever run into any web browser compatibility issues?
A few of my blog visitors have complained about my site not working correctly in Explorer but looks
great in Chrome. Do you have any advice to help fix this issue?
I really love your site.. Excellent colors & theme.
Did you create this web site yourself? Please reply back as I’m attempting to create my
own site and would love to find out where you got this from or what the theme is named.
Thank you!
Hello there, I found your site by means of Google whilst searching for a similar matter, your site came up,
it appears good. I have bookmarked it in my google bookmarks.
Hi there, just turned into aware of your blog thru Google,
and located that it’s really informative. I’m gonna watch out for brussels.
I’ll appreciate if you happen to continue this in future.
A lot of folks shall be benefited out of your writing.
Cheers!
You actually make it seem so easy along with your presentation however I in finding this topic to
be really something which I believe I might never understand.
It kind of feels too complicated and extremely large for me.
I’m having a look ahead to your next put up, I will try to get the hang of it!
It’s really very difficult in this active life to
listen news on Television, therefore I just use the web for that
purpose, and take the newest information.
Thank you, I have just been looking for information approximately this subject for a long time and yours is
the best I’ve found out so far. However, what in regards to the bottom line?
Are you positive about the supply?
Heya i am for the first time here. I found this board and I find It really useful & it helped me out much.
I hope to give something back and help others like you aided me.
Definitely believe that which you said. Your favorite justification seemed to be on the net the
simplest thing to be aware of. I say to you, I definitely
get irked while people consider worries that they plainly don’t know about.
You managed to hit the nail upon the top
as well as defined out the whole thing without having side-effects
, people can take a signal. Will probably be back to get more.
Thanks
If some one wants to be updated with latest technologies therefore he must be visit this web site and be up to date all the
time.
Thanks for sharing your thoughts. I really appreciate your efforts and I am
waiting for your further write ups thanks once again.
Its not my first time to pay a quick visit this web page,
i am visiting this web site dailly and get good data from here everyday.
Hey! I’m at work surfing around your blog from my new apple iphone!
Just wanted to say I love reading your blog and look
forward to all your posts! Carry on the fantastic work!
my web site gabapentin 100mg
Everything is very open with a really clear clarification of the challenges.
It was really informative. Your site is extremely helpful.
Many thanks for sharing!
Aw, this was an exceptionally nice post. Spending some time and actual
effort to make a good article… but what can I say… I procrastinate a whole lot and never
manage to get nearly anything done.
Pretty nice post. I just stumbled upon your weblog and wanted to
say that I have really enjoyed surfing around your blog posts.
After all I’ll be subscribing to your rss feed and I hope you write again soon!
听话水/乖乖水/催情/迷昏/迷幻/迷情药出售QQ微信同号343116263乙醚七氟烷 日本,美国代购。乖乖水,听话水,开心水,迷幻,媚药,FM2,三唑仑,GHB,唛可奈因,催情,喷雾型,失忆型,无记忆型,伪装型催情口香糖,咖啡,香水等,正品进口日本性素,男用壮阳,延迟,情趣器具等各类成人情趣用品(详情讯息咨询)全海外代购正品货源,日本欧美av专用等产品。所有属情趣产品,请勿用于非法用途!QQ微信同号343116263帮你搞定女神搞定小可爱
Если вы рассматриваете возможность покупки спецодежды в Абакане, то вам стоит обратить внимание
на местные магазины и сервисы, специализирующиеся
на этом виде продукции. В городе есть несколько магазинов, предлагающих широкий выбор спецодежды,
которая может соответствовать вашим потребностям и требованиям.
Перед приобретением спецодежды
важно определить ее цель и требования.
В зависимости от сферы деятельности,
вам может понадобиться защита от различных факторов:
пожара, химических веществ, статического электричества, падающих предметов
и других потенциальных опасностей.
Уточните ваши требования перед посещением магазинов.
В Абакане можно найти специализированные магазины, предлагающие широкий ассортимент спецодежды для различных отраслей: строительства, промышленности,
медицины, горнодобывающей
промышленности и других. Изучите предложения каждого магазина и выберите тот, который предлагает спецодежду, соответствующую вашим требованиям.
Качество спецодежды является важным фактором при выборе.
Убедитесь, что выбранный вами магазин сотрудничает с надежными производителями, производящими качественную и сертифицированную продукцию.
Хорошие магазины готовы предоставить информацию о производителях и стандартах безопасности.
I like the helpful info you provide in your articles. I will bookmark your weblog and check again here regularly.
I’m quite certain I’ll learn a lot of new stuff right here!
Best of luck for the next!
Pretty nice post. I just stumbled upon your weblog and wanted to
say that I have really enjoyed surfing around your blog posts.
After all I’ll be subscribing to your rss feed and I hope you write again soon!
This is my first time pay a visit at here
and i am really impressed to read everthing at single place.
Genuinely no matter if someone doesn’t be aware of after that
its up to other visitors that they will assist, so here it takes place.
Usually I do not learn article on blogs, but I would like to say that
this write-up very compelled me to check out and do so!
Your writing style has been amazed me. Thank you, quite great article.
Thanks. I like it.
Feel free to visit my blog post: https://www.cydiafree.com/
I really like your blog.. very nice colors & theme. Did you create this website yourself or did you hire someone to do it for you?
Plz answer back as I’m looking to construct my own blog and
would like to find out where u got this from. thanks a lot
Wow, marvelous blog layout! How long have you been blogging for?
you make blogging look easy. The overall look of your website is magnificent,
as well as the content!
像你这样的人,为何不去研究易经和64进制?世界在不停的变化中。从名字就可以看出,易经讲的就是变化。而易经里有八八六十四卦,周而复始。所以用现在的话来说他就是一个64进制的东西。若是用你的才能研究研究这个,那比什么千禧问题有用多了。
哈哈哈哈哈哈哈
(很遗憾评论区已经被机器人淹没了)
感谢博主的讲解,感觉这次对P和NP问题的理解又更清晰了一些。
我想评论主要还是因为“最后,不要高兴得太早”段落,因为我惊讶的发现这些设想正在被目前突飞猛进的AI技术逐渐实现:AI已经能自然的与人交流,有人还尝试过让AI学会非常小众的语言,只要提供很有限的资料,AI就能掌握这门语言,甚至包含资料中未提及的词语,我甚至怀疑已经有人开始训练AI“凭感觉”解密RSA算法……
只需要有限的训练数据,AI就能在该领域对答如流,这不正是文中描述的想象中的场面么。
不过目前的AI还是会产生“幻觉”和误判,或许也表明AI并不能掌握所有的解,依然充满悬念。
更进一步,在网络上,你再也没法把人和人区别开来,甚至没法把人和计算机区别开来。计算机不仅能轻易通过图灵测试(Turing test),还能精确地模仿某一个特定的人。如果你能把某个人的网络聊天记录全部搜集起来,把这个人和网友们的对话全部递交给计算机,计算机将会很快学会如何模仿这个人。网络的身份鉴定必须要借助物理手段。即使是在科幻故事中,这样的设定也相当疯狂,可见 P = NP 有多不可能了。
———-
还是写得太早了,现在LLM已经可以做到了