可计算性理论与复杂性导论

本文概述

• 可计算性
• 复杂度
• 总结

你是否曾经想过：你正在阅读本文的设备到底是什么？电脑是什么？

计算科学的历史可以追溯到甚至还没有想到这些现代计算设备的时间。在这个行业中, 最常见的问题围绕编程语言, 框架和库进行, 我们经常理所当然地认为构成计算机壁虱的基本概念。

但是这些似乎具有无限潜力的计算机-是否有任何限制？是否存在无法使用计算机解决的问题？

在本文中, 我们将通过脱离编程语言和计算机体系结构的细节来解决这些问题。通过了解计算机和算法的功能和局限性, 我们可以改善思考的方式并更好地推理出不同的策略。

计算的抽象观点所产生的结果经受了时间的考验, 对于今天的我们来说, 就像在1970年代最初开发时一样有价值。

可计算性

电脑是什么？有什么问题吗？

在学校里, 我们经常被教给一个问题和功能的心理模型, 它是这样的：

函数是应用于输入x以查找输出f(x)的过程。

原来的数学定义是不同的：

函数是一组有序对, 使得每对的第一个元素来自集合X(称为域), 每对的第二个元素来自集合Y(称为共域或范围), 并且每个元素域与范围内的一个元素配对。

那是满口的。但是, 这到底是什么意思？

这个定义告诉我们计算机是用于计算功能的机器。

为什么？

因为计算机将任意输入转换为某些输出。换句话说, 他们解决了问题。函数的两个定义(我们非常熟悉的一个和形式上的)在许多实际目的上是一致的。

但是, 数学定义可以使我们得出有趣的结论, 例如存在无法计算的函数(即, 无法解决的问题)：

因为, 并非每个函数都可以描述为一种算法。

游戏规则

为了帮助我们进行论证, 让我们将计算机想象成是接受一些输入, 执行一系列操作以及一段时间后给出一些输出的机器。

我们将输入内容称为机器的字母；也就是一组有限的一组字符串。例如, 机器的字母可以是二进制(0和1), 也可以是ASCII字符集。任何有限的字符序列都是字符串, 例如” 0110″。

此外, 我们将机器的输出表示为二进制接受/拒绝决策, 一旦机器完成(有希望)完成计算, 就将其交付。这种抽象非常适合早期的函数的数学定义。

给定这些参数, 表征另一种类型(字符串的集合)非常重要。也许我们关心某个机器可以接受的字符串集, 或者我们正在构建一个可以接受某个集合中的字符串但不接受其他字符串的机器, 或者我们在问是否有可能设计一个可以接受某个字符串中的所有内容的机器。特别设置, 没有其他。

在所有这些情况下, 一组字符串称为一种语言-例如, 所有表示偶数的二进制字符串的集合或具有偶数个字符的字符串的集合。事实证明, 可以使用诸如串联, 联合, 交集之类的运算符来操作诸如数字之类的语言。

一个重要的运算符是Kleene star运算符, 该运算符也用于正则表达式。这可以被认为是语言所有可能力量的结合。例如, 如果我们的语言A是字符串{’01’, ‘1’}的集合, 那么A *的一个成员就是字符串’0101111’。

可数性

在我们证明并非所有功能都是可计算的主张之前, 最后一个难题是可数性的概念。凭直觉, 我们的证明将显示出更多的语言。也就是说, 问题多于可能的解决方案。之所以可行, 是因为字符串是否属于某种语言(是/否)本身就是一个问题。

更准确地说, 我们的证明声称, 可能的程序集是无限多个的, 而字母表中的语言集是无限多个的。

此时, 你可能会想：”无限本身本身就是一个足够奇怪的想法；现在我必须处理其中两个！”

好吧, 还不错。可数的无限集是可以枚举的。可以说这是第一个元素, 这是第二个元素, 依此类推, 最终为集合中的每个元素分配了一个数字。例如, 以偶数集为例。我们可以说2是第一个, 4是第二个, 6是第三个, 依此类推。这样的集合是无限的或可数的。

但是, 对于某些集合, 例如实数, 你的聪明程度并不重要；根本就没有枚举。这些集合是无限或无限的。

无数的程序

首先, 我们要证明计算机程序集是可数的。出于我们的目的, 我们通过观察有限字母上的所有字符串的集合是可数的来做到这一点的。这是可行的, 因为计算机程序本身就是有限字符串。

证明很简单, 我们不在这里介绍细节。关键要点在于, 存在的计算机程序与自然数一样多。

重申：

任何字母上的所有字符串的集合(例如, 所有计算机程序的集合)是可数的。

无数种语言

根据这个结论, 这些字符串的子集又如何呢？问另一种方式, 所有语言集如何？事实证明, 这个集合是不可数的。

任何字母上所有语言的集合都是不可数的。

再一次, 我们不在这里证明。

后果

尽管可能无法立即看出来, 但语言不可数和所有计算机程序集可数性的后果是深远的。

为什么？

假设A是ASCII字符集； ASCII字符就是组成计算机程序所需的字符。我们可以看到, 代表JavaScript程序的字符串集是A *的子集(此处, *是Kleene星运算符)。 JavaScript的选择是任意的。由于这套程序是可数集的子集, 因此我们认为这套JavaScript程序是可数的。

另外, 让我们考虑一下, 对于任何语言L, 我们都可以定义一些函数f, 如果某些字符串x位于L中, 则该函数f的值为1, 否则为0。所有这些功能都是不同的。因为与所有语言的集合存在1：1的对应关系, 并且由于所有语言的集合都是不可数的, 所以所有这些函数的集合都是不可数的。

这是重点：

由于所有有效程序的集合都是可数的, 而函数集不是可计数的, 因此必须存在一些我们根本无法编写程序的函数。

我们尚不知道这些功能或问题是什么样子, 但我们知道它们存在。这是一个令人毛骨悚然的实现, 因为那里存在一些无法解决的问题。我们认为计算机非常强大, 并且功能强大, 但是有些东西甚至超出了它们的承受范围。

现在的问题变成：”这些问题是什么样的？”在继续描述此类问题之前, 我们必须首先以通用方式对计算进行建模。

图灵机

艾伦·图灵(Alan Turing)开发了计算机的最早的数学模型之一。这种称为图灵机的模型是一种非常简单的设备, 完全体现了我们的可计算性概念。

机器的输入是已在其上写入输入的磁带。机器使用读/写头, 通过一系列步骤将输入变成输出。在每个步骤中, 都会决定是否向磁带写入内容以及向磁带写入什么内容以及向右或向左移动磁带。该决定完全基于两件事：

• 头部下方的当前符号, 以及

• 机器的内部状态, 也会随着符号的写入而更新

而已。

普遍性

1926年, 艾伦·图灵(Alan Turing)不仅开发了图灵机, 而且在撰写著名论文《论可计算数字》时对计算的本质也有其他许多重要见解。他意识到, 计算机程序本身可以被认为是计算机的输入。基于这种观点, 他有一个很漂亮的想法, 那就是图灵机可以模拟或执行该输入。

虽然我们今天将这些想法视为理所当然, 但在图灵时代, 这种通用机器的想法是一项重大突破, 使图灵能够解决无法解决的问题。

教会图论

在继续之前, 让我们检查一个重要的点：我们知道图灵机是一种计算模型, 但是它是否足够通用？为了回答这个问题, 我们转向Church-Turing论文, 该论文证明了以下说法：

一切可计算的东西都可以由图灵机计算。

在图灵将图灵机开发为计算模型的同时, 阿隆佐·丘奇还开发了称为lambda演算的计算模型。这些模型功能强大, 因为它们都描述了计算, 并且以与当今任何计算机或就此而言任何计算机相同的方式进行计算。这意味着我们可以使用图灵机来描述我们要解决的不可解决的问题, 因为我们的发现将适用于过去, 现在和以后的所有可能的计算机。

可识别性和可判定性

在我们具体描述一个无法解决的问题, 即语言识别器和语言决定者的概念之前, 我们需要覆盖更多背景知识。

如果有图灵机可以识别该语言, 则该语言是可识别的。如果有图灵机来决定语言, 则该语言是可决定的。

为了成为语言的识别者, 图灵机必须接受该语言中的每个字符串, 并且不得接受任何非该语言中的字符。它可能拒绝或在此类字符串上循环。要成为决策者, 图灵机必须始终通过接受或拒绝来停止其输入。

在这里, 暂停输入的想法至关重要。实际上, 我们看到决策者比识别者更强大。此外, 问题可以解决, 或者换句话说, 仅当存在确定该功能描述的语言的图灵机时, 该功能才可以确定。

不确定性

如果你曾经编写过计算机程序, 那么一定要知道执行该程序时只是看着计算机转动轮子而坐在那里的感觉。你不知道该程序是不是花了很长时间, 还是代码中有错误导致无限循环。你甚至可能想知道为什么编译器不检查代码以查看其在运行时是否会永远停止或循环。

编译器没有这种检查, 因为它根本无法完成。并不是说编译器工程师不够聪明或缺乏资源；根本不可能检查任意计算机程序以确定它是否停止。

我们可以使用图灵机证明这一点。图灵机可以描述为字符串, 因此它们的数量很多。假设M1, M2等组成所有图灵机的集合。让我们定义以下函数：

如果Mi接受<Mj>, 则f(i, j)= 1, 否则为0

在此, <M>是” M的字符串编码”的语法, 并且此函数表示如果Mi停止接受Mj作为输入而输出1, 否则输出0的问题。请注意, Mi必须停下来(即成为决策者)。这是必需的, 因为我们希望描述一个不确定的函数(即, 无法解决的问题)。

现在, 让我们还定义一种语言L, 它由不接受其自身描述的图灵机的字符串编码组成：

L = {<M> | M不接受<M>}

例如, 某些机器M1可能在输入<M1>上输出0, 而另一台机器M2可能在输入<M2>上输出1。为了证明这种语言是无法确定的, 我们问决定语言L的机器ML在输入自​​己的描述<ML>作为输入时会做什么。有两种可能性：

ML接受<ML>或ML拒绝<ML>

如果ML接受自己的编码, 则表示<ML>不在语言L中；反之, 但是, 如果是这种情况, 那么ML最初不应该接受其编码。另一方面, 如果ML不接受其自己的编码, 则<ML>使用语言L, 因此ML应该已经接受了其字符串编码。

在这两种情况下, 我们都有一个悖论, 或者说在数学上是一个矛盾, 证明了语言L是无法确定的。因此, 我们描述了第一个无法解决的问题。

停止问题

尽管我们刚刚描述的问题似乎无关紧要, 但可以将其简化为具有实际重要性的其他无法解决的问题, 最显着的问题是停顿问题：

停止在空字符串上的图灵机的编码语言。

暂停问题适用于为什么编译器无法从早期检测到无限循环的问题。如果我们无法确定程序是否以空字符串终止, 那么如何确定程序的执行是否会导致无限循环？

在这一点上, 似乎我们只是挥手示意一些简单的结论。但是, 我们实际上意识到, 图灵机无法判断计算机程序将永远停止还是保持循环。这是实际应用中的重要问题, 无法在图灵机或任何其他类型的计算机上解决。 iPhone无法解决此问题。具有多个核心的桌面无法解决此问题。云无法解决此问题。即使有人发明了量子计算机, 它仍然无法解决停顿问题。

摘要

在我们对可计算性理论的考察中, 我们看到了有多少个函数无法通过计数论点在任何普通意义上计算。我们精确地定义了计算的含义, 并从图灵的笔和纸经验一直追溯到图灵的灵感, 从而使图灵机正式化。我们已经看到了该模型如何计算当今或将来设想的任何计算机可以执行的任何操作, 并且我们认识到一类根本无法计算的问题。

尽管如此, 可计算性还是有缺点。仅仅因为我们可以解决问题, 并不意味着我们可以迅速解决。毕竟, 如果计算机无法在未来几千万年的太阳升空之前完成计算, 对计算机有什么好处？

抛开可计算的功能和语言, 我们现在讨论计算复杂性, 调查有效的计算以及著名的P vs. NP问题。

复杂度

慢与快

计算机科学家认识到各种类型的问题, 我们关注的两类问题包括计算机可以快速或有效解决的问题(称为P)和可以快速验证但无法迅速获得其解决方案的问题(称为NP)。

例如, 假设你负责开发在线约会服务的算法, 并且有人提出了一个问题：”每个人都能得到约会吗？”答案归结为配对兼容的个人, 以便每个人都配对。事实证明, 有解决此问题的有效算法。此问题在集合P中。

好吧, 如果我们想确定用户中最大的集团怎么办？所谓集团, 是指彼此兼容的最大个人网络。当用户数较少时, 可以快速解决此问题。我们可以轻松地识别出一个拥有3个用户的集团。但是, 随着我们开始寻找更大的集团, 这个问题变得越来越难解决。这个问题在集合NP中。

正式定义

P是在多项式时间内可以解决的一组问题。即, 关于问题的大小, 计算步骤的数量由多项式函数限制。我们知道”每个人都可以约会吗？”问题, 也称为二分匹配问题, 在P中。

NP是可在多项式时间内验证的一组问题。当然, 这包括P中的每个问题。但是, 我们不知道这种限制是否严格。我们知道可以有效验证但无法有效解决的问题, 但是我们不知道问题是否真正棘手。集团问题就是这样的问题之一。我们知道我们可以有效地验证解决方案, 但是我们不确定是否可以有效地解决问题。

最后, NP完全问题是NP中最困难的问题。之所以将它们称为最困难的, 是因为NP中的任何问题都可以有效地转化为NPC。结果, 如果有人要确定NPC中问题的有效解决方案, 则整个NP类都会被P吸收。集团问题也存在于NPC中。

因此, 我们得出了P vs. NP的问题。许多计算机科学家和数学家坚信P和NP不相等。如果是这样, 其影响将是深远的。当今的大多数数字基础结构都依赖于这样的事实, 即NP中存在一些问题, 而P中没有这些问题。例如, 如果不是这种情况, 则加密方法将在一夜之间崩溃, 从而使人们可以有效地解决NPC问题甚至破坏最严格的安全协议。

易操作性

对于计算机科学新手来说, 匹配问题和群体问题之间的区别似乎并不大。实际上, P中的问题与NP中的问题之间的差异可能非常微妙。能够分辨出差异对于设计现实世界中的任何算法都很重要。

考虑最短路径问题。给定两个位置, 目标是确定它们之间的最短路径。 iPhone只需几毫秒即可计算出一次。这是一个在计算上容易处理的问题。

另一方面, 请考虑旅行推销员问题, 该问题的目的是在以尽可能短的距离行进的同时访问以终点为起点的可能目的地的子集。这个问题与最短路径问题相似, 但是是NP完全问题。它也解释了为什么供应链物流是一个十亿美元的产业。

实际上, 我们甚至可以变得更加微妙。除了求最短路径(P)外, 我们还可以求没有循环的最长路径。原来最长路径问题也是NP完全的。

这种微妙区别的更多示例, 包括在二部图和通用图中识别顶点覆盖, 或每个子句使用两个或三个文字来满足布尔公式。关键是, 问题到底出在P还是NP尚不是很明显, 这就是为什么运行时间分析是关键技能。如果必须针对P中的问题设计算法, 那么我们知道有一个有效的解决方案。另一方面, 如果问题出在NP上, 那么我们就有理由反对追求解决方案, 因为一般而言, 该算法将花费很长时间来解决问题。

摘要

在对复杂性的检查中, 我们定义了问题P和NP的类别。 P非正式地表示可以由计算机有效解决的问题, 而NP表示可以有效验证的问题。

没有人能够证明P不等于NP。这两类问题是否相等, 被称为P vs. NP问题, 如果不是所有的数学方法, 这也是当今理论计算机科学中最重要的开放问题。实际上, 在2000年, 克莱数学学院将P vs. NP问题列为数学中最重要的七个开放问题之一, 并提供了上百万美元的赏金, 作为确定该问题解决方案的证据。

总结

在本文中, 我们深入研究了可计算性和复杂性领域, 回答了诸如”什么是计算机？”之类的大问题。尽管细节可能令人不知所措, 但仍有许多值得铭记的重要收获：

• 有些事情根本无法计算, 例如暂停问题。

• 有些事情无法有效地计算, 例如NPC中的问题。

比细节更重要的是思考计算和计算问题的方式。在我们的职业生活中, 甚至在我们的日常生活中, 我们可能会遇到从未见过的问题, 并且我们可以使用久经考验的真实工具和技术来确定最佳的解决方案。