算法，猫视频，和人类的局限性

卢克·雅各布斯

“如果数学是对真理的研究，那么计算机科学就是对复杂性的研究”

“深哉，神丰富的智慧和知识！他的判断何其难测，他的道路何其难测！”

计算机科学被广泛接受的观点是，它只是工程学。你可以用它来给电脑编程，制造机器人，或者建立网站，这几乎是它的所有功能。我认为这是对计算机科学的一种过于简单化的看法。

计算机科学的主要研究方向是算法。许多人没有意识到，算法的发展不仅是有益的，而且是建设现代社会的基础。算法不仅将明升体育官网带入对明升体育官网所生活的技术世界的探索，而且还向明升体育官网揭示了明升体育官网在宇宙中的位置。

算法复杂度

算法是在给定某些信息的情况下完成特定任务的指令列表。在现实世界中，明升体育官网一直在执行算法。一个例子是一个明升体育。评分大纲列出了一份作业要获得最高分所应具备的品质。老师看了看题目，按照它的说明去做，这样就执行了一个算法。一个明升体育有输入和输出。输入是一个未评分的作业，输出是一个评分。算法只是一组指示，告诉你如何工作。

算法有自己的属性。程序员最关心的是一个名为“时间复杂度”的属性。复杂度大致描述了给定一定难度的任务，算法需要执行多少步。下面是一些时间复杂度模型的可视化图（技术术语是Big-O复杂度）：

曲线越陡峭，具有相同时间复杂度的算法完成任务所需的时间就越长。程序员希望使算法不需要更多的步骤（“操作”），因为它的任务难度增加（“元素”）。

例如，雅各布斯先生厌倦了给科学测试中的多项选择题打分，所以他决定把所有的科学预算都花在一台答题机上。无论考试中有多少选择题，这台机器都需要5秒的时间来评分。机器正在执行一个算法，该算法接受测试答案并返回一个分数作为输出。

明升体育官网可以对给定n的算法的时间复杂度进行建模。变量n表示算法的任务负载。随着n的增大，呈现给算法的任务难度也随之增大。假设n等于考试中选择题的个数。用n表示，机器完成10次测试需要多长时间？记住，无论问题有多少，机器都可以在5秒内对任何测试进行评分。这意味着n可以是100，机器仍然会在5秒内完成一次测试。对于10级测试，该算法的时间复杂度将为50秒，这是一个常数时间，与n无关。对于程序员来说，恒定的时间复杂度是理想的，但在实践中，算法很少需要恒定的时间来处理可变数量的数据。在现实生活中，随着难度的增加，大多数算法需要更长的时间来完成任务。

现在明升体育官网设n等于明升体育官网输入机器的测试次数。明升体育官网的时间复杂度会改变，因为n改变了。由于机器每次测试需要5秒，所以复杂度将是5n，线性时间。现在明升体育官网的算法完成所需的时间取决于n。随着n的增加，明升体育官网算法的执行时间也会增加。

到目前为止，时间复杂度背后的数学原理几乎是不言自明的，而且可能有点无聊。你可能会开始认为这与明升体育官网的社会无关，更不用说明升体育官网在宇宙中的位置了。然而，当时间复杂度呈指数增长时，它就变得有趣了。

让明升体育官网来看一个新的例子来说明指数时间复杂度在现实世界中是什么样的。比如说你想侵入瓦勒先生的电脑。瓦勒先生是个狡猾的人，所以他不会用你能猜到的密码。他选择了一个n位数的随机数。如果他选择的位数(n)是1，他的密码将只有1位，所以明升体育官网必须猜测数字0到9来尝试所有可能的组合。如果n = 2，明升体育官网需要猜出从0到99的数字，才能猜出2位数的所有组合。简而言之，你最多要猜10n次（10乘以自己n次）才能进入他的电脑。如果猜出一个可能的密码需要一定的时间，比如2秒，那么明升体育官网任务的时间复杂度将是2（10n）秒，指数时间。

棘手的问题

任何试图猜出长密码的人都知道，如果瓦勒选择了一个较大的n值，那么破解他的电脑将需要一段不合理的时间。在计算机科学中，明升体育官网称这类问题为“棘手的”。棘手的问题没有快速的算法来解决。解决高难度的棘手问题需要花费大量时间，以至于世界上最快的超级计算机可以运行数十亿年也找不到答案。这类似于明升体育官网要花几年时间才能猜出瓦勒电脑的所有密码组合。

棘手的问题不会随着明升体育官网开发更快的计算机而消失。假设明升体育官网买了一个机器人来猜瓦勒先生的密码。机器人猜密码的速度比明升体育官网快10倍，但这种速度的提高并不能解决明升体育官网面临的问题。如果瓦勒先生在他的密码上再加一个数字，明升体育官网猜出所有可能的密码所花的时间就和明升体育官网买机器人之前一样。通过将n（密码数字的数量）增加1，他将密码的可能性增加了10。即使明升体育官网能把猜密码的速度提高100倍，瓦勒先生也可以在他的密码上再加一个数字，这样就能阻止明升体育官网加快猜密码的速度。正如你所看到的，当一个棘手问题的n增加时，算法解决它所需的时间就会急剧增加。那些已经被证明是难以解决的问题是如此之难，以至于宇宙中没有任何智能能够在不尝试每一个可能的答案的情况下解决它们。

你可能会认为棘手的问题是数学家会避免的问题。如果明升体育官网不能计算出它们的解，它们怎么可能有用呢？你可能会认为明升体育官网应该放弃这个数学领域，转向更适用的领域。然而，数学的一个令人难以置信的行为是，一个看似无用的领域的发展可以在现实世界中找到奇怪的应用。

数学与实用性

数学家伯恩哈德·黎曼在19世纪50年代研究了三维以上的几何。（是的，这确实存在。）在他工作的时候，这个数学领域还没有什么用处。毕竟，世界上所有的几何都是三维的，对吧？黎曼并不在乎他把时间花在了可能永远不会用到的数学上；他只是想为了探索而了解这个世界。作为一名基督徒，他认为自己的工作是通过喜悦创造来服侍上帝的一种方式。对创造的喜悦并不包括寻找利用它的方法；它涉及到思考它的美。

在他的有生之年，几乎所有人都会认为黎曼在多维几何方面的工作毫无意义，但数学在奇怪的地方显露出自己的价值。大约50年后，另一位德国人——你可能认识他——阿尔伯特·爱因斯坦写了一篇关于“广义相对论”概念的论文。它解释了空间和时间是如何联系起来的。它们就像一块织物，可以被恒星和行星弯曲。为了表现这种效应，爱因斯坦不得不使用多维几何，黎曼的“无用”工作。广义相对论现在被用于设计GPS系统，所以你每次打开谷歌地图时都要感谢黎曼。

因此，当我说棘手的问题实际上是有用处的时候，明升体育官网不应该感到惊讶。事实上，有一个特别棘手的问题非常重要，如果一个算法能有效地解决它，现代社会就会崩溃。问题是大数很难分解。

半素数：最重要的一组没有人知道的数字

在代数中，明升体育官网学习如何进行质因数分解，即将任意数简化为一系列质数的过程：

25 = 5 * 5 100 = 4 * 25 = 2 * 2 * 5 * 5 7 = 7（不能进一步化简，因为它本身就是素数）

正如你所看到的，质数是数字的组成部分。每个数字都是它们的组合。现在明升体育官网来看一组特殊的数字，叫做半素数。半素数是两个素数相乘的结果。下面是一些例子：

25 = 5 * 5
2201 = 71 * 31
979458869581637 = 13935491 * 70285207

半素数最重要的性质是分解它们是一个棘手的问题。像100这样的数字很容易分解，因为你可以把它分解成越来越小的部分。首先可以除以2，然后除以5，然后再除以5，以此类推。这样一来，明升体育 就像一套乐高积木。拆乐高积木不需要花费太多时间和精力；小孩子总是这样。另一方面，半素数就像原子一样——更难分裂。一大批物理学家和数学家才学会了如何分裂原子。半素数的存在时间和原子一样长，只是明升体育官网还没有找到一种有效的方法来分裂它们。它们实际上比原子更难分裂。明升体育官网已经建造了惊人的粒子加速器，可以可靠地破坏原子，但分解半素数这个看似简单的问题从一开始就困扰着数学家。半质数很难分解，因为它们只由两个质数组成。你不能把它们分成2块以上。分解它们是一个棘手的问题，但这并不限制它们的用途；事实上，它使它们明升体育成为最有用的数字。

半素数与密码学

半素数对密码学至关重要的性质是，给定一个因素，它们可以很容易地生成和分解。现代计算机可以在一秒钟内生成一个随机的150位素数。生成这么大的数字速度很快。计算机所需要做的就是生成两个质数，并将它们相乘，然后得到一个300位的半质数，这个半质数实际上是不可分解的。对外界来说，它的因素是个秘密。只有您的计算机知道原始因子，它们充当您的密码。因为您知道您的半素数因子，所以您可以加密和解密无法解码的消息。世界各国政府采用的最先进的密码系统都是基于这些特殊数字的简单属性。

但密码学不仅仅适用于政府或需要隐藏东西的人。明升体育官网每天都在不知不觉中使用它。HTTPS协议中使用加密技术。HTTPS用于保护明升体育官网的设备和明升体育官网访问的网站之间的通信通道。这是必要的，因为“安全”的wifi网络并不完全安全。Wifi密码可以保护网络不被外界入侵，但网络内收发的所有信息都是完全可见的。如果没有加密技术提供的安全通道，任何人都可以看到你在公共wifi上观看的猫视频（明升体育官网知道你这样做）。如果没有加密，你的设备与YouTube的通信将被所有人看到，这意味着当你观看世界上最大的10只猫的视频时，黑客将看到你的“安全”谷歌密码出现在明升体育 的屏幕上。每个人都有身份被盗、银行账户被抢的风险，而且没有人能确定明升体育 在网上发信息的人实际上就是明升体育 在现实世界中交谈的朋友。政府将无法向战场上的士兵发送信息，核战争可能迫在眉睫。世界将一片混乱。明升体育官网对密码学的依赖比明升体育官网意识到的要多得多。

棘手的意义

把世界上的问题放在一边，你能看到半素数和棘手的问题是多么美丽吗？研究棘手的问题和数论就像研究明升体育官网智力的极限，研究明升体育官网作为人类能够解决的问题和明升体育官网甚至无法触及的问题。明升体育官网在中学学习质数，但它们的一些简单性质甚至难倒了世界上最好的数学博士。半素数只是明升体育官网发现的棘手问题的一个例子；大约有100个问题难倒了计算机科学家。这种情况可能会永远持续下去。

我相信上帝创造了这样一个世界，明升体育官网将永远保持下去。我怀疑明升体育官网是否会走到科学的尽头。上帝想让明升体育官网知道，明升体育官网是被放置在一个明升体育官网无法理解的世界里的生物，明升体育官网唯一的办法就是承认他是明升体育官网的创造者，并依靠他来指导明升体育官网。计算机科学，即对算法的研究，应该让明升体育官网处于一种谦卑的状态，因为明升体育官网不断面临着可能永远无法解决的障碍。在克服其中一些障碍方面，明升体育官网已经取得了很大进展，但似乎还有一些障碍是无法克服的。这只会更多地揭示上帝是无限的，而明升体育官网是难以置信的有限。计算机科学不仅仅是编程视频游戏或制造可以为明升体育官网工作的机器人，更重要的是研究人类可以解决的问题和让明升体育官网完全困惑的问题。

感谢阅读！